POJ 1236
给定一个有向图，求：
1) 至少要选几个顶点，才能做到从这些顶点出发，可以到达全部顶点
2) 至少要加多少条边，才能使得从任何一个顶点出发，都能到达全部顶点
第一个就是缩点之后有多少入度为0的个数因为一定要从这些节点出发
第二个就是因为图本身就是联通的，设入度为0的点有n个，出度为0的点有m个，
那么入度的编号为N0,N1,N2,N3...Nn,出度编号为M0,M1,M2...Mm
那么连N0->M0->N1->M1->N2->M3。这样形成环啦那连到Min(n,m)时就会结束了剩下的Abs（n-m）点，连起来就有Max(n,m)个点啦.
#include <cstring>
const int Maxn=;
const int Maxm=;
struct EDGE{int to,next;}edge[Maxm<<];
int head[Maxn],Dfn[Maxn],Low[Maxn],Belong[Maxn],In[Maxn],Out[Maxn],Stack[Maxn],Top,vis[Maxn],n,cnt,Stamp,Scc,x;
inline int Max(int x,int y) {return x>y?x:y;}
inline int Min(int x,int y) {return x>y?y:x;}
inline void Add(int u,int v) {edge[cnt].to=v;edge[cnt].next=head[u];head[u]=cnt++;} void Tarjan(int u,int fa)
{
Low[u]=Dfn[u]=++Stamp; Stack[++Top]=u; vis[u]=true;
for (int i=head[u];i!=-;i=edge[i].next)
{
int v=edge[i].to;
if (v==fa) continue;
if (!Dfn[v])
{
Tarjan(v,u);
Low[u]=Min(Low[u],Low[v]);
} else if (vis[v]) Low[u]=Min(Low[u],Dfn[v]);
}
if (Dfn[u]==Low[u])
{
Scc++; int v=;
while (v!=u)
{
v=Stack[Top--];
vis[v]=false;
Belong[v]=Scc;
}
}
}
int main()
{
// freopen("c.in","r",stdin);
scanf("%d",&n);
memset(head,-,sizeof(head));
for (int i=;i<=n;i++)
while (scanf("%d",&x)&&x)
Add(i,x);
memset(vis,false,sizeof(vis)); Scc=;
for (int i=;i<=n;i++) if (!Dfn[i]) Tarjan(i,);
for (int u=;u<=n;u++)
for (int i=head[u];i!=-;i=edge[i].next)
if (Belong[u]!=Belong[edge[i].to]) In[Belong[edge[i].to]]++,Out[Belong[u]]++;
int Tmp1=,Tmp2=;
for (int i=;i<=Scc;i++)
{
if (In[i]==) Tmp1++;
if (Out[i]==) Tmp2++;
}
if (Scc==)
{
puts("");
puts("");
return ;
}
printf("%d\n",Tmp1);
printf("%d\n",Max(Tmp1,Tmp2));
return ;
}
POJ 1236
POJ 3177
给定一个连通的无向图G，至少要添加几条边，才能使其变为双连通图。
Tarjan缩点后统计叶子节点的个数，给两个相连就可以了 所以Sum=(Ans+1)>>1;
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int Maxn=;
const int Maxm=;
struct EDGE{int to,next;}edge[Maxm<<];
int head[Maxn],Dfn[Maxn],Low[Maxn],vis[Maxn],n,m,u,v,cnt,Top,Stack[Maxn],d[Maxn],Scc,Stamp,Belong[Maxn],Ans;
inline void Add(int u,int v) {edge[cnt].to=v;edge[cnt].next=head[u];head[u]=cnt++;}
inline int Min(int x,int y) {return x>y?y:x;} void Tarjan(int u,int fa)
{
Dfn[u]=Low[u]=++Stamp; Stack[++Top]=u; vis[u]=true;
for (int i=head[u];i!=-;i=edge[i].next)
{
int v=edge[i].to;
if (i==(fa^)) continue;
if (!Dfn[v])
{
Tarjan(v,i);
Low[u]=Min(Low[u],Low[v]);
} else if (vis[v]) Low[u]=Min(Low[u],Dfn[v]);
}
if (Dfn[u]==Low[u])
{
Scc++;
while (true)
{
int v=Stack[Top--];
vis[v]=false;
Belong[v]=Scc;
if (v==u) break;
}
}
}
int main()
{
scanf("%d%d",&n,&m);
memset(head,-,sizeof(head));
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 u=;u<=n;u++)
{
for (int i=head[u];i!=-;i=edge[i].next)
if (Belong[u]!=Belong[edge[i].to]) d[Belong[u]]++;
}
for (int i=;i<=Scc;i++) if (d[i]==) Ans++;
printf("%d\n",(Ans+)>>);
return ;
}
POJ 3177
POJ 1144
给你一个图，求有多少个割点
u为树根，且u有多于一个子树。 (2) u不为树根，且满足存在(u,v)为树枝边(或称父子边，即u为v在搜索树中的父亲)，使得DFS(u)<=Low(v)。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int Maxn=;
const int Maxm=;
struct EDGE{int to,next;}edge[Maxm];
int head[Maxn],Dfn[Maxn],Low[Maxn],Root,Son,u,v,n,cnt,Stamp;
bool Cut[Maxn];
inline int Min(int x,int y) {return x>y?y:x;}
inline void Add(int u,int v) {edge[cnt].to=v;edge[cnt].next=head[u];head[u]=cnt++;}
void Tarjan(int u)
{
Dfn[u]=Low[u]=++Stamp;
for (int i=head[u];i!=-;i=edge[i].next)
{
int v=edge[i].to;
if (!Dfn[v])
{
Tarjan(v);
if (u==Root) Son++;
else
{
Low[u]=Min(Low[u],Low[v]);
if (Dfn[u]<=Low[v]) Cut[u]=true;
}
} else
Low[u]=Min(Low[u],Dfn[v]);
}
}
int main()
{
while (scanf("%d",&n)!=EOF && n!=)
{
memset(head,-,sizeof(head));
memset(Dfn,,sizeof(Dfn));
memset(Low,,sizeof(Low));
memset(Cut,false,sizeof(Cut)); Stamp=; cnt=;
while (scanf("%d",&u)!=EOF && u!=)
while (getchar()!='\n')
{
scanf("%d",&v);
Add(u,v),Add(v,u);
}
Root=,Son=;
Tarjan();
int Ans=;
if (Son>) Ans=;
for (int i=;i<=n;i++) if (Cut[i]) Ans++;
printf("%d\n",Ans);
}
return ;
}
POJ 1144
POJ 2186
求出度为0的奶牛的个数即可
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int Maxn=;
const int Maxm=;
struct EDGE{int to,next;}edge[Maxm<<];
int n,m,Dfn[Maxn],Low[Maxn],head[Maxn],Stack[Maxn],Belong[Maxn],Scc,Stamp,cnt,Top,u,v,Out[Maxn],vis[Maxn],Size[Maxn];
inline void Add(int u,int v) {edge[cnt].to=v;edge[cnt].next=head[u]; head[u]=cnt++;}
inline int Min(int x,int y) {return x>y?y:x;}
void Tarjan(int u)
{
Dfn[u]=Low[u]=++Stamp; Stack[++Top]=u; vis[u]=true;
for (int i=head[u];i!=-;i=edge[i].next)
{
int v=edge[i].to;
if (!Dfn[v])
{
Tarjan(v);
Low[u]=Min(Low[u],Low[v]);
} else
if (vis[v])
Low[u]=Min(Low[u],Dfn[v]);
}
if (Dfn[u]==Low[u])
{
Scc++;
int v=;
while (v!=u)
{
v=Stack[Top--];
Belong[v]=Scc,++Size[Scc];
vis[v]=false;
}
}
}
int main()
{
scanf("%d%d",&n,&m);
memset(head,-,sizeof(head));
for (int i=;i<=m;i++)
{
scanf("%d%d",&u,&v);
Add(u,v);
}
for (int i=;i<=n;i++)
if (!Dfn[i]) Tarjan(i);
for (int u=;u<=n;u++)
{
for (int i=head[u];i!=-;i=edge[i].next)
if (Belong[u]!=Belong[edge[i].to]) Out[Belong[u]]++;
}
int Zero=,k=;
for (int i=;i<=Scc;i++)
if (!Out[i])
{
Zero++;
k=Size[i];
}
Zero>?puts(""):printf("%d\n",k);
return ;
}
POJ2186
POJ 3352
一个连通的无向图，求至少需要添加几条边，救能保证删除任意一条边，图仍然是连通的，即成为双连通分量
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int Maxn=;
const int Maxm=;
struct EDGE{int to,next;}edge[Maxm<<];
int head[Maxn],Dfn[Maxn],Low[Maxn],vis[Maxn],n,m,u,v,cnt,Top,Stack[Maxn],d[Maxn],Scc,Stamp,Belong[Maxn],Ans;
inline void Add(int u,int v) {edge[cnt].to=v;edge[cnt].next=head[u];head[u]=cnt++;}
inline int Min(int x,int y) {return x>y?y:x;}
void Tarjan(int u,int fa)
{
Dfn[u]=Low[u]=++Stamp; Stack[++Top]=u; vis[u]=true;
for (int i=head[u];i!=-;i=edge[i].next)
{
int v=edge[i].to;
if (v==fa) continue;
if (!Dfn[v] && !vis[v])
{
Tarjan(v,u);
Low[u]=Min(Low[u],Low[v]);
} else if (vis[v]) Low[u]=Min(Low[u],Dfn[v]);
}
if (Dfn[u]==Low[u])
{
Scc++;
while (Stack[Top]!=u && Top>=) Belong[Stack[Top--]]=Scc;
Belong[Stack[Top--]]=Scc;
}
}
int main()
{
scanf("%d%d",&n,&m);
memset(head,-,sizeof(head));
for (int i=;i<=m;i++)
{
scanf("%d%d",&u,&v);
Add(u,v),Add(v,u);
}
Tarjan(,);
for (int u=;u<=n;u++)
{
for (int i=head[u];i!=-;i=edge[i].next)
if (Belong[u]!=Belong[edge[i].to]) d[Belong[edge[i].to]]++;
} for (int i=;i<=Scc;i++) if (d[i]==) Ans++;
printf("%d\n",(Ans+)>>);
return ;
}
POJ 3352
HDU 3394
一个无向图(可能不连通)有n个点和m条边.现在要你找出冲突边和多余边的数目.其中冲突边是那些同时存在于多个环中的边,而多余边是不在任何一个环中的边.当点数=边数，形成一个环，当点数>边数（一条线段，说明这条边是桥），当点数<边数，那么就含1个以上的环了
#include <cstdio>
#include <cstring>
const int Maxn=;
const int Maxm=;
const int Inf=0x3f3f3f3f;
int Low[Maxn],Dfn[Maxn],Bcc[Maxn],vis[Maxn],Stamp,Top,cnt,u,v,Bridge,Way;
int head[Maxn],Stack[Maxn],n,m,belong[Maxn];
struct EDGE{int to,next;}edge[Maxm<<];
inline int Min(int x,int y) {return x>y?y:x;}
inline void Add(int u,int v)
{edge[cnt].to=v;edge[cnt].next=head[u];head[u]=cnt++;}
inline void CirCuit()
{
int Cnt=;
memset(belong,false,sizeof(belong));
for (int i=;i<=Bcc[];i++) belong[Bcc[i]]=true;
for (int j=;j<=Bcc[];j++)
{
int u=Bcc[j];
for (int i=head[u];i!=-;i=edge[i].next)
if (belong[edge[i].to]) Cnt++;
}
Cnt>>=;
if (Cnt>Bcc[]) Way+=Cnt;
}
void Tarjan(int u,int fa)
{
Low[u]=Dfn[u]=++Stamp; Stack[++Top]=u; vis[u]=true;
for (int i=head[u];i!=-;i=edge[i].next)
{
int v=edge[i].to;
if (fa==(i^)) continue;
if (!Dfn[v])
{
Tarjan(v,i);
Low[u]=Min(Low[u],Low[v]);
if (Low[v]>=Dfn[u])
{
if (Low[v]>Dfn[u]) Bridge++;
Bcc[]=;
while (true)
{
int x=Stack[Top--];
Bcc[++Bcc[]]=x;
if (x==v) break;
}
Bcc[++Bcc[]]=u;
CirCuit();
}
} else if (vis[v]) Low[u]=Min(Low[u],Dfn[v]);
}
}
int main()
{
while (scanf("%d%d",&n,&m)!=EOF)
{
if (n== && m==) break;
cnt=; memset(head,-,sizeof(head));
memset(Dfn,,sizeof(Dfn)); Top=;
memset(Low,,sizeof(Low)); Stamp=;
memset(vis,false,sizeof(vis));
Bridge=Way=;
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,-);
printf("%d %d\n",Bridge,Way);
}
return ;
}
HDU 3394