tarjan 求强连通分量
#include#include #include using namespace std;vector hh[10000];struct tonod{ int p,next;}g[1000],v[10000];int top=1,time=0,st[10000],top2=0,num=0;int dfn[10000],low[10000];bool inst[10000];int insert(int x,int y){ v[top].p=y; v[top].next=g[x].next; g[x].next=top; top++;}void tarjan(int u){ time++; dfn[u]=time; low[u]=time; st[++top2]=u; inst[u]=1; for(int i=g[u].next;i!=-1;i=v[i].next) { int t=v[i].p; if(!dfn[t]) { tarjan(t); low[u]=min(low[u],low[t]); } else if(inst[t]) low[u]=min(low[u],dfn[t]); } if(dfn[u]==low[u]) { int k; num++; do { k=st[top2--]; hh[num].push_back(k); inst[k]=0; } while(k!=u); }}int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) g[i].next=-1; for(int i=1;i<=m;i++) { int a,b; scanf("%d%d",&a,&b); insert(a,b); } tarjan(1); for(int i=1;i<=num;i++) { printf("("); for(int j=0;j
tarjan求无向图割边
当且仅当dfn[u]<low[v] 时，边<u,v>为割边
注意更新low时判断v是否是u的父亲，如果是则不更新low
#include#include #include using namespace std;struct tonod{ int p,next;}g[1000],v[1000];struct nn{ int a,b;}ans[10000];bool w[1000][1000];int top=1,time1=0,num=0;int dfn[1000],low[1000];int insert(int x,int y){ v[top].next=g[x].next; v[top].p=y; g[x].next=top; top++;}void tarjan(int u,int a){ time1++; dfn[a]=time1; low[a]=time1; for(int i=g[a].next;i!=-1;i=v[i].next) { int t=v[i].p; if(!dfn[t]) { tarjan(a,t); low[a]=min(low[a],low[t]); if(dfn[a]
tarjan求无向图割点
1.当dfn[u]<=low[v]时，点u为割点
2.当根节点有两个以上子树时，根节点为割点
同样注意更新low时判断v是否是u的父亲，如果是则不更新low
代码:
1 #include2 #include 3 #include 4 using namespace std; 5 struct tonod{ 6 int p,next; 7 }v[1000000]; 8 int head[1000000],dfn[1000000],low[1000000]; 9 int top=1,n,m,mytime=0;10 bool visit[1000000];11 int ans[1000000],num=0;12 void set()13 {14 for(int i=1;i<=n;i++)15 head[i]=-1;16 }17 void insert(int x,int y)18 {19 v[top].next=head[x];20 v[top].p=y;21 head[x]=top;22 top++;23 }24 void tarjan(int f,int u)25 {26 mytime++;27 dfn[u]=mytime;low[u]=mytime;28 int children=0;29 for(int i=head[u];i!=-1;i=v[i].next)30 {31 int t=v[i].p;32 if(dfn[t]==0)33 {34 children++;35 tarjan(u,t);36 low[u]=min(low[u],low[t]);37 if(u!=1&&dfn[u]<=low[t]&&visit[u]==0)38 {39 num++;40 ans[num]=u;41 visit[u]=1;42 }43 }44 else45 if(t!=f)46 low[u]=min(dfn[t],low[u]);47 }48 if(u==1&&children>=2)49 {50 num++;51 ans[num]=1;52 }53 }54 void init()55 {56 scanf("%d",&n);57 set();58 int a,b;59 while(scanf("%d%d",&a,&b)!=EOF)60 {61 insert(a,b);62 insert(b,a);63 } 64 }65 void outit()66 {67 printf("%d\n",num);68 sort(ans+1,ans+num+1);69 for(int i=1;i<=num;i++)70 printf("%d\n",ans[i]);71 }72 int main()73 {74 init();75 tarjan(0,1);76 outit();77 }
