前排Orz tarjan
tarjan算法在图的连通性方面有非常多的应用，dfn和low数组真是奥妙重重（并没有很搞懂反正背就完事了）
有向图强连通分量
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<stack>
using namespace std;
struct edge{
int v,next;
}a[];
stack<int>s;
int n,m,u,v,sum=,tt=-,ans=,h[],anss[],num[],nums[],tot=,tim=,dfn[],low[],head[];
bool used[],isin[];
void tarjan(int u){
int v;
used[u]=isin[u]=true;
low[u]=dfn[u]=++tim;
s.push(u);
for(int tmp=head[u];tmp!=-;tmp=a[tmp].next){
v=a[tmp].v;
if(!used[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}else{
if(isin[v])low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u]){
v=-;
sum++;
while(v!=u){
v=s.top();
s.pop();
isin[v]=;
num[v]=sum;
nums[sum]++;
}
}
}
void add(int u,int v){
a[++tot].v=v;
a[tot].next=head[u];
head[u]=tot;
}
int main(){
memset(used,,sizeof(used));
memset(head,-,sizeof(head));
memset(h,-,sizeof(h));
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
scanf("%d%d",&u,&v);
add(u,v);
}
for(int i=;i<=n;i++){
if(!used[i])tarjan(i);
}
tot=;
for(int i=;i<=n;i++){
for(int tmp=head[i];tmp!=-;tmp=a[tmp].next){
if(num[i]!=num[a[tmp].v]){
h[num[i]]=++tot;
}
}
}
for(int i=;i<=sum;i++){
if(nums[i]>)ans++;
}
printf("%d\n",ans);
for(int i=;i<=sum;i++){
if(h[i]==-){
if(tt!=-||nums[i]==){
tt=-;
break;
}else tt=i;
}
}
if(tt==-)printf("-1");
else for(int i=;i<=n;i++){
if(num[i]==tt)printf("%d ",i);
}
return ;
}
无向图割点
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
struct edge{
int v,next;
}a[];
int t=,n,s,ss,u,v,tim=,sum=,tot=,head[],dfn[],low[];
bool f=false,used[],ff[];
void add(int u,int v){
a[++tot].v=v;
a[tot].next=head[u];
head[u]=tot;
}
void tarjan(int u,int fa){
int v;
dfn[u]=low[u]=++tim;
for(int tmp=head[u];tmp!=-;tmp=a[tmp].next){
v=a[tmp].v;
if(!low[v]){
tarjan(v,u);
if(u==)sum++;
low[u]=min(low[u],low[v]);
if(u!=&&dfn[u]<=low[v]){
ff[u]=true;
}
}else if(v!=fa){
low[u]=min(low[u],dfn[v]);
}
}
}
void dfs(int u){
int v;
used[u]=true;
for(int tmp=head[u];tmp!=-;tmp=a[tmp].next){
v=a[tmp].v;
if(!used[v])dfs(v);
}
}
int main(){
while(scanf("%d",&s)&&s){
printf("Network #%d\n",++t);
memset(head,-,sizeof(head));
memset(ff,,sizeof(ff));
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
tot=n=sum=tim=;
f=false;
scanf("%d",&ss);
add(s,ss);
add(ss,s);
n=max(n,max(s,ss));
scanf("%d",&s);
while(s){
scanf("%d",&ss);
add(s,ss);
add(ss,s);
n=max(n,max(s,ss));
scanf("%d",&s);
}
tarjan(,-);
if(sum>)ff[]=true;
for(int i=;i<=n;i++){
if(ff[i]){
memset(used,,sizeof(used));
f=used[i]=true;
sum=;
for(int j=;j<=n;j++){
if(!used[j]){
sum++;
dfs(j);
}
}
printf(" SPF node %d leaves %d subnets\n",i,sum);
}
}
if(!f){
printf(" No SPF nodes\n");
}
printf("\n");
}
return ;
}
/*
1 2
5 4
3 1
3 2
3 4
3 5
0 1 2
2 3
3 4
4 5
5 1
0 1 2
2 3
3 4
4 6
6 3
2 5
5 1
0 0
--------
Network #1
SPF node 3 leaves 2 subnets Network #2
No SPF nodes Network #3
SPF node 2 leaves 2 subnets
SPF node 3 leaves 2 subnets
*/
无向图点双连通分量
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#include<stack>
using namespace std;
struct edge{
int v,next;
}a[];
struct edge1{
int u,v;
};
int n,m,u,v,tot=,tim=,bcctot=,bccnum[],head[],dfn[],low[],iscut[];
vector<int>ans[];
stack<edge1>s;
void add(int u,int v){
a[++tot].v=v;
a[tot].next=head[u];
head[u]=tot;
}
void tarjan(int u,int fa){
edge1 t;
int v,son;
dfn[u]=low[u]=++tim;
for(int tmp=head[u];tmp!=-;tmp=a[tmp].next){
v=a[tmp].v;
if(v==fa)continue;
t.u=u;
t.v=v;
if(!dfn[v]){
s.push(t);
son++;
tarjan(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]){
iscut[u]=true;
ans[++bcctot].clear();
while(true){
edge1 tt=s.top();
s.pop();
if(bccnum[tt.u]!=bcctot){
ans[bcctot].push_back(tt.u);
bccnum[tt.u]=bcctot;
}
if(bccnum[tt.v]!=bcctot){
ans[bcctot].push_back(tt.v);
bccnum[tt.v]=bcctot;
}
if(tt.u==u&&tt.v==v)break;
}
}
}else if(dfn[v]<low[u]){
s.push(t);
low[u]=min(low[u],dfn[v]);
}
}
if(fa<&&son==)iscut[u]=false;
}
int main(){
memset(iscut,,sizeof(iscut));
memset(head,-,sizeof(head));
memset(low,,sizeof(low));
memset(bccnum,,sizeof(bccnum));
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
tarjan(,-);
for(int i=;i<=bcctot;i++){
printf("%d:",i);
for(int j=;j<ans[i].size();j++){
printf("%d ",ans[i][j]);
}
printf("\n");
}
return ;
}
/*
6 7
1 2
2 3
1 3
3 4
4 5
3 5
5 6
--------
1:5 6
2:4 3 5
3:2 1 3
*/
无向图求桥
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
struct edge{
int u,v,next;
}a[];
int n,m,u,v,tot=,tim=,head[],dfn[],low[],ansu[],ansv[];
void add(int u,int v){
a[++tot].u=u;
a[tot].v=v;
a[tot].next=head[u];
head[u]=tot;
}
void tarjan(int u,int fa){
int v;
dfn[u]=low[u]=++tim;
for(int tmp=head[u];tmp!=-;tmp=a[tmp].next){
v=a[tmp].v;
if(dfn[v]==){
tarjan(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u]){
ansu[++ansu[]]=u;
ansv[++ansv[]]=v;
}
}else{
if(dfn[v]<dfn[u]&&v!=fa){
low[u]=min(low[u],dfn[v]);
}
}
}
}
int main(){
memset(head,-,sizeof(head));
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
ansu[]=;
ansv[]=;
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
tarjan(,-);
printf("--------\n");
for(int i=;i<=ansv[];i++){
printf("%d %d\n",ansu[i],ansv[i]);
}
return ;
}
/*
6 7
1 2
2 3
1 3
3 4
4 5
5 6
6 4
--------
3 4
*/
无向图边双连通分量
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
struct edge{
int v,next;
}a[];
int n,m,u,v,tot=,tim=,num=,head[],dfn[],low[],bl[];
bool used[],bri[];
vector<int>g[];
void add(int u,int v){
a[++tot].v=v;
a[tot].next=head[u];
head[u]=tot;
}
void tarjan(int u,int fa){
int v;
dfn[u]=low[u]=++tim;
for(int tmp=head[u];tmp!=-;tmp=a[tmp].next){
v=a[tmp].v;
if(dfn[v]==){
tarjan(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u]){
bri[tmp]=true;
bri[tmp^]=true;
}
}else{
if(dfn[v]<dfn[u]&&v!=fa){
low[u]=min(low[u],dfn[v]);
}
}
}
}
void dfs(int u){
used[u]=true;
bl[u]=num;
g[num].push_back(u);
for(int tmp=head[u];tmp!=-;tmp=a[tmp].next){
int v=a[tmp].v;
if(bri[tmp])continue;
if(!used[v])dfs(v);
}
}
int main(){
memset(head,-,sizeof(head));
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(used,,sizeof(used));
memset(bri,,sizeof(bri));
memset(bl,,sizeof(bl));
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
for(int i=;i<=n;i++){
if(!dfn[i])tarjan(i,-);
}
for(int i=;i<=n;i++){
if(!used[i]){
num++;
dfs(i);
}
}
for(int i=;i<=num;i++){
printf("%d: ",i);
for(int j=;j<g[i].size();j++)printf("%d ",g[i][j]);
printf("\n");
}
return ;
}