本文共 1446 字，大约阅读时间需要 4 分钟。
呐呐，既然是模板那也没什么好说的了，直接看代码里的东西吧~~
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 using namespace std;20 const int N=100001;21 22 int n,m,tot,ans;23 int h[N],dfn[N],low[N],fa[N];24 bool vis[N];25 struct node{26 int v;27 int next;28 }e[2*N];29 30 void add(int u,int v){//加边31 tot++;32 e[tot].next=h[u],33 e[tot].v=v,34 h[u]=tot;35 }36 37 void tarjan(int p){//tarjan+缩点38 int t=0;39 dfn[p]=low[p]=++tot;40 for(int i=h[p];i;i=e[i].next){41 int v=e[i].v;42 if(!dfn[v]){43 fa[v]=fa[p];44 tarjan(v);45 low[p]=min(low[p],low[v]);46 if(low[v]>=dfn[p]&&p!=fa[p]){//在回溯后立即更新47 vis[p]=true;48 }49 if(p==fa[p]){//特殊情况50 t++;51 }52 }53 low[p]=min(low[p],dfn[v]);54 }55 if(p==fa[p]&&t>=2){56 vis[fa[p]]=true;57 }58 }59 60 int main(){61 scanf("%d%d",&n,&m);62 for(int i=1;i<=m;i++){63 int x,y;64 scanf("%d%d",&x,&y);65 add(x,y);//无向图，加两次边66 add(y,x);67 }68 for(int i=1;i<=n;i++){69 fa[i]=i;70 }71 tot=0;72 for(int i=1;i<=n;i++){73 if(!dfn[i]){74 tarjan(i);75 }76 }77 for(int i=1;i<=n;i++){78 if(vis[i]){79 ans++;80 }81 }82 printf("%d\n",ans);83 for(int i=1;i<=n;i++){84 if(vis[i]){85 printf("%d ",i);86 }87 }88 return 0;89 }
没了。。
转载于:https://www.cnblogs.com/hahaha2124652975/p/11155018.html