Description
Input
Output
Sample Input
3 3 1 3 2 3 3 1 2 1 1 2 0
Sample Output
1 3 2
思路:求强连通后缩点,然后求出度为0 的点就行,出度为0的点在强连通之前可能有多个点的,所以在Tarjan中需要把强连通的那些点记录下来,以便在求出度为0的点使用。
感想:这题WA了十多发,从昨晚做一直到现在都是Wa,搞不明白是什么回事。还以为是边界错了,但是都改了也不对。然后刚才一句一句的看,才发现写代码的时候,在Tarjan算法中把min写成了max,然后LOW数组就错了。靠!!!!!细节搞死人啊,手误就误了一天了!!!!
#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <list> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #define PI acos(-1.0) #define mem(a,b) memset(a,b,sizeof(a)) #define sca(a) scanf("%d",&a) #define pri(a) printf("%d\n",a) #define MM 10002 #define MN 5005 #define INF 168430090 using namespace std; typedef long long ll; int n,m,cnt,tem,Count,DFN[MN],LOW[MN],od[MN],vis[MN],suo[MN],q2[MN]; vector<int>q[MN],p[MN]; void tarjan(int u) { int j,v; DFN[u]=LOW[u]=++cnt; vis[u]=1; q2[++tem]=u; for(j=0; j<q[u].size(); j++) { v=q[u][j]; if(!DFN[v]) { tarjan(v); LOW[u]=min(LOW[u],LOW[v]); //把min写成了max然后导致错了十多发 } else if(vis[v]&&DFN[v]<LOW[u]) LOW[u]=DFN[v]; } if(DFN[u]==LOW[u]) { Count++; do { v=q2[tem--]; vis[v]=0; p[Count].push_back(v); //连通结点记录下来 suo[v]=Count; //缩点,属于同一个强连通则缩成新的一个结点 } while(v!=u); } } void solve() { int v,i,j; Count=cnt=tem=0; mem(DFN,0); for(i=1; i<=n; i++) if(!DFN[i]) tarjan(i); for(i=1; i<=n; i++) //此循环在缩点的基础上,如果需要重新建图就可以重新建图,这里不需要重新建图 for(j=0; j<q[i].size(); j++) { v=q[i][j]; if(suo[v]!=suo[i]) od[suo[i]]++; //不属于同一个强连通 } } int main() { int i,j,u,v,sum; while(sca(n)&&n) { sca(m); set<int>s; set<int>::iterator it; for(i=0; i<=n; i++) q[i].clear(),p[i].clear(); mem(od,0); mem(LOW,0); mem(vis,0); mem(suo,0); for(i=0; i<m; i++) { scanf("%d%d",&u,&v); q[u].push_back(v); } solve(); for(i=1; i<=Count; i++) if(od[i]==0) //如果出度为0,即从u可以到v,v也可以到u,题目是这个意思,在图论中就是缩点后出度为0 { for(j=0; j<p[i].size(); j++) s.insert(p[i][j]); //因为set自动从小到大排序,所以引用 } for(it=s.begin(),sum=0; it!=s.end(); it++) { cout<<*it; sum++; if(sum<s.size()) cout<<‘ ‘; } cout<<endl; } return 0; }
CUGB图论专场2:The Bottom of a Graph 强连通Tarjan算法
原文:http://blog.csdn.net/u011466175/article/details/19483085