求解强联通分量（网易2020校招）

求解强联通分量（网易2020校招）

//求解相连通分量
int dfn[101]; // 记录每个节点的访问顺序
int low[101]; // 记录所属强连通的数组low
bool instack[101]; // 每个节点是否在表中
stack<int> sta;
vector<int> edge[101]; // 表示每个节点的邻接节点表
vector<int> belong[101]; // belong[1] 表示第一组，最多每个不想连，有101组
int cnt = 0, cntb = 0;
void dfs(int u)
{cnt++;dfn[u] = cnt;low[u] = cnt;  sta.push(u);instack[u] = true;for(int i = 0; i<edge[u].size();i++){int v = edge[u][i];if(!dfn[v]){dfs(v);low[u] = min(low[u],low[v]);}else if(instack[v]){low[u] = min(low[u],dfn[v])}}if(low[u] == dfn[u]){cntb++;int tmp;do{tmp = p();stack.pop();instatck[tmp] = false;belong[cntb].push_back(tmp);}while(tmp != u)}}