要写一段算strong connected nodes的代码
在数据少的时候没有错误,但是vertices有80w个的时候,在递归的某一步出现奇怪的错误,从调用堆栈看应该是从vector里取数字的时候出现错误。
在数据少的时候没有错误,但是vertices有80w个的时候,在递归的某一步出现奇怪的错误,从调用堆栈看应该是从vector里取数字的时候出现错误。
#include<iostream> #include<vector> #include<fstream> #include<map> using namespace std; #define N 875714 //875714 int t = 0, s = 0; int timels[N]; int maxedgesize = 0; class vertice { public: vertice() { exp = false; edgesize = 0; } int ID; int ftime; int leader; vector<int> edge; int edgesize; bool exp; void add(int); void setID(int); }; void vertice::add(int a) { edge.push_back(a); edgesize++; if (edgesize > maxedgesize) maxedgesize = edgesize; } void vertice::setID(int a) { ID = a; } void DFS(vertice*g, int i,int step) { g[i - 1].exp = true; g[i - 1].leader = s; for (int n = 0; n < g[i - 1].edgesize; n++) { vector<int>::iterator it = g[i - 1].edge.begin(); int temp = *(it+n); if (!g[temp - 1].exp) { DFS(g, temp,step); } } t++; g[i - 1].ftime = t; if(step==1) timels[t - 1] = i; } void DFS_Loop(vertice*g,int step) { t = 0; s = 0; for (int r = 0; r < N; r++) { int exc; if (step == 1) { exc = r + 1; } else { exc = timels[N -1 - r]; } if (!g[exc - 1].exp) { s = exc; DFS(g, exc,step); } } } void Fcount(vertice*g) { map<int, int> temp; typedef map<int, int> fuck; for (int i = 0; i < N; i++) { int leader = g[i].leader; temp[leader] += 1; } for (fuck::iterator i = temp.begin();i!=temp.end();i++) { std::cout << i->first << " " << i->second << endl; } } int main() { vertice *g = new vertice[N]; vertice *gr = new vertice[N]; for (int i = 0; i < N;i++) { g[i].setID(i + 1); gr[i].setID(i + 1); } ifstream fh("c://Users//burni//Desktop//scc.txt", ios::in); while (!fh.eof()) { int tail; int head; fh >> tail >> head; g[head - 1].add(tail); gr[tail - 1].add(head); } DFS_Loop(gr,1); DFS_Loop(g, 2); Fcount(g); delete[] g, gr; return 0; }
错误在45行,原本本人是用的[]来取数字的,出错之后改成这样(有点蠢)还是错,不知道怎么回事,求高手帮助。
解决方案
100
1.修改栈大小
2.改为非递归实现