爱在心中

2019-11-06 08:41:34

字体：大中小

来源：转载

供稿：网友

#include<cstdio>#include<vector>using namespace std;int top=0;int dfn[99999];int low[99999];int colour[99999];int dfn_num;int ans;int colour_num;int vis[99999];int strak[99999];int f[1999][1999];int r[999999];int flag[99999];vector < int > a[99999];vector < int > b[99999]; void dfs(int x){ dfn[x]=++dfn_num; low[x]=dfn_num; vis[x]=1; strak[++top]=x; for(int i=0;i<a[x].size();i++) { int temp=a[x][i]; if(!dfn[temp]) { dfs(temp); low[x]=min(low[x],low[temp]); } else if(vis[temp]) { low[x]=min(low[x],low[temp]); } } if(dfn[x]==low[x]) { vis[x]=0; int t=0; colour[x]=++colour_num; while(strak[top]!=x) { vis[strak[top]]=0; colour[strak[top--]]=colour_num; t++; } top--; if(t>=1) ans++,flag[colour_num]=1; }} int n,m;int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); a[x].push_back(y); } for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i); PRintf("%d/n",ans); //for(int i=1;i<=n;i++)// printf("%d ",colour[i]); ans=0;int z; for(int j=1;j<=n;j++) { for(int i=0;i<a[j].size();i++) if(f[colour[j]][colour[a[j][i]]]==0&&colour[j]!=colour[a[j][i]]) { b[colour[j]].push_back(colour[a[j][i]]);//缩点 f[colour[j]][colour[a[j][i]]]=1; r[colour[j]]++; } } for(int i=1;i<=colour_num;i++) { if(r[i]==0&&flag[i]==1) //找出度为零的点 { z=i; ans++; } } if(ans==1) { for(int j=1;j<=n;j++) if(colour[j]==z) printf("%d ",j);//输出 } //for(int i=1;i<=colour) else printf("-1"); return 0;}

这个题的思路是用tarjan缩点然后找出度为零的一个点这个题有传递性，就是说a爱b，b爱c，a就爱c。

上一篇：5. Longest Palindromic Substring （Medium）

下一篇：解决CSDN博客中代码块开头出现标签代码问题