正題

題目鏈接:https://www.luogu.org/problemnew/show/P1726

---

題目大意

求最大的強聯通分量和包含的點

---

解題思路

$tarjan$模板不解釋。

---

$code$

#include<cstdio> #include<algorithm> #include<stack> using namespace std; const int N=5010,M=50100; struct node{int to,next; }a[2*M]; stack<int> Stack; int n,m,tot,cnt,num,ans,mark; int ls[N],dfn[N],low[N],siz[N],in[N]; bool v[N]; void addl(int x,int y) {a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot; } void tarjan(int x) {Stack.push(x);v[x]=1;dfn[x]=low[x]=++cnt;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(!dfn[y]){tarjan(y);low[x]=min(low[x],low[y]);}else if(v[y])low[x]=min(low[x],dfn[y]);}if(low[x]==dfn[x]){++num;while(Stack.top()!=x){int y=Stack.top();Stack.pop();in[y]=num;siz[num]++;v[y]=0;}Stack.pop();v[x]=0;siz[num]++;in[x]=num;} } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);addl(x,y);if(z>1) addl(y,x);}for(int i=1;i<=n;i++)if(!dfn[i]) tarjan(i);for(int i=1;i<=n;i++)if(siz[in[i]]>ans){ans=siz[in[i]];mark=in[i];}printf("%d\n",ans);for(int i=1;i<=n;i++)if(in[i]==mark) printf("%d ",i);}

總結

以上是生活随笔為你收集整理的P1726-上白泽慧音【tarjan,图论】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。