题目描述
输入样例
3 3 1 3 2 3 3 1 2 1 1 2 0
输出样例
1 3 2
思路
G中任意两个点都可到达,则G是图的一个强连通分量.sink点就是强连通分量中的点.题目要求是输出sink点.
所以我们应该先通过Tarjan算法找到强连通分量,然后缩点,统计每个(缩点)的出度,最后缩点出度为1的那些点就是我们要求的sink点.
参考代码
#include<iostream> #include<stack> #include<string.h> using namespace std; const int maxn = 5000+10; int n,m; int head[maxn],num,ins[maxn],low[maxn],dfn[maxn],cnt,belong[maxn],id,degree[maxn];//ins:标记是否在 stack中 stack<int> s; struct Edge{ int to,next; }e[maxn*maxn]; void add(int u,int v){ e[++num].next = head[u]; e[num].to = v; head[u] = num; } void tarjan(int u){ low[u] = dfn[u] = ++cnt; ins[u] = 1; s.push(u); for(int i = head[u]; i ; i = e[i].next){ int v = e[i].to; if(!dfn[v]){ tarjan(v); low[u] = min(low[u],low[v]); }else if(ins[v]){ low[u] = min(low[u],low[v]); } } if(low[u]==dfn[u]){//缩点 int v; do{ v = s.top(); s.pop(); belong[v] = id; ins[v] = 0; }while(u!=v); id++; } } void init() { memset(head,0,sizeof(head)); memset(ins,0,sizeof(ins)); memset(low,0,sizeof(low)); memset(dfn,0,sizeof(dfn)); memset(belong,0,sizeof(belong)); memset(degree,0,sizeof(degree)); num = cnt =0; id = 1; } void solveDegree(){//求出度 for(int u = 1; u <= n; u++){ for(int i = head[u]; i; i = e[i].next){ int v = e[i].to; if(belong[u]!=belong[v]){//如果u和v的连通分量号不同 degree[belong[u]]++;//u节点所在的连通分量号的出度++ } } } } void print(){//输出 int flag = 1; for(int i = 1;i <= n; i++){ if(!degree[belong[i]]){//如果出度为0则说明是连通分量 if(flag){//第一个数据前没有空格 flag = 0; }else{ cout<<" "; } cout<<i; } } cout<<endl; } int main(){ int u,v; while(cin>>n&&n){ cin>>m; while(m--){ cin>>u>>v; add(u,v); } for(int i = 1; i <= n; i++){ if(!dfn[i]){ tarjan(i); } } solveDegree(); print(); init(); } return 0; }
