求强连通分量-korasaju算法

Love The Way You Lie 2021-11-10 02:16 309阅读 0赞

## 基本思路 ##

两次dfs，第一次逆序，第二次计算连通分量的类别。待完善。

#include<bits/stdc++.h> using namespace std; typedef struct{ int vertex,next; }NODE;NODE nodes[10010]; int end[10010]={0},m,n,index,color[10010]={0},vis[10010]={0}; vector<int>v; void dfs(int cur) { //cout<<"cur="<<cur<<"index="<<index<<endl; priority_queue<int,vector<int>,greater<int> >q; for(int i=0;i<m;i++) { if(nodes[i].vertex==cur) {//当前顶点 if(!vis[nodes[i].next]) {//未遍历 vis[nodes[i].next]=1; q.push(nodes[i].next); } } } while(!q.empty()) { end[q.top()]=index; index--; v.push_back(q.top()); dfs(q.top()); q.pop(); } } void dfs2(int cur) { //cout<<"cur="<<cur<<"index="<<index<<endl; priority_queue<int,vector<int>,greater<int> >q; for(int i=0;i<m;i++) { if(nodes[i].vertex==cur) { if(vis[nodes[i].next]==1) { q.push(nodes[i].next); } } } vis[cur]=0; color[cur]=index; while(!q.empty()) { dfs2(q.top()); q.pop(); } } int main() { cin>>n>>m; for(int i=0;i<m;i++) {//读取边 cin>>nodes[i].vertex>>nodes[i].next; } index=n; for(int i=1;i<=n;i++) { if(!vis[i]) {//未遍历 vis[i]=1; end[i]=index; index--; v.push_back(i); dfs(i); } } // for(int i=1;i<=n;i++) // { // cout<<end[i]<<" "; // } // cout<<endl; // for(vector<int>::iterator it=v.begin();it!=v.end();it++) // { // cout<<(*it)<<" "; // } // cout<<endl; for(vector<int>::iterator it=v.end()-1;it!=v.begin()-1;it--) {//逆向遍历 if(vis[(*it)]==1) { vis[(*it)]=0; color[(*it)]=index; index++; dfs2((*it)); } } cout<<"强连通分量："<<endl; stack<int>qlt[7]; for(int i=1;i<=n;i++) { qlt[color[i]].push(i); } for(int i=1;i<=n;i++) { if(qlt[i].empty())continue; else while(!qlt[i].empty()) { cout<<qlt[i].top()<<" "; qlt[i].pop(); } cout<<endl; } return 0; }

转载于:https://www.cnblogs.com/tldr/p/11144758.html