POJ 2762 Going from u to v or from v to u?
题意:判断该图的任意两点是否可达
分析:tarjan后进行缩点,缩点后再建图,判断该图是否为单链式图形(只有一个叶结点) 判断能到达该点的节点个数是否等于bcnt
#include<stdio.h>
#include<string.h>
#include<vector>
#include<stack>
using namespace std;
const int MN=2011;
vector<int>edge[MN];
vector<int>SCC[MN];
stack<int>s;
int low[MN],dfn[MN];
int instack[MN],stap[MN];
int belong[MN];
int num[MN];
int ind[MN];
int tp,p;
int bcnt;
void tarjan(int x)
{
low[x]=dfn[x]=++tp;
stap[++p]=x;
instack[x]=1;
for(int i=0;i<edge[x].size();i++)
{
int v=edge[x][i];
if(dfn[v]==-1)
{
tarjan(v);
if(low[x]>low[v])
low[x]=low[v];
}
else if(instack[v] && dfn[v]<low[x])
low[x]=dfn[v];
}
if(low[x]==dfn[x])
{
int top;
do
{
top=stap[p];
belong[top]=bcnt;
instack[top]=0;
p--;
}while(x!=top);
bcnt++;
}
}
void topsort()
{
memset(num,0,sizeof(num));
int i,u,v;
while(!s.empty())
s.pop();
for(int i=0;i<bcnt;i++)
if(ind[i]==0)
{
s.push(i);
num[i]++;
}
while(!s.empty())
{
u=s.top();
s.pop();
for(int i=0;i<SCC[u].size();i++)
{
v=SCC[u][i];
if(--ind[v]==0)
{
s.push(v);
num[v]=num[u]+1;
}
}
}
}
int main()
{
int T,n,m,i,a,b,j;
scanf("%d",&T);
while(T--)
{
bcnt=tp=p=0;
scanf("%d%d",&n,&m);
memset(dfn,-1,sizeof(dfn));
memset(low,0,sizeof(low));
memset(instack,0,sizeof(instack));
memset(belong,0,sizeof(belong));
memset(ind,0,sizeof(ind));
for(i=1;i<=n;i++)
{
edge[i].clear();
SCC[i].clear();
}
for(i=0;i<m;i++)
{
scanf("%d%d",&a,&b);
edge[a].push_back(b);
}
for(i=1;i<=n;i++)
{
if(dfn[i]==-1) tarjan(i);
}
for(i=1;i<=n;i++)
{
for(j=0;j<edge[i].size();j++)
{
int x=belong[i];
int y=belong[edge[i][j]];
if(x!=y)
{
SCC[x].push_back(y);
ind[y]++;
}
}
}
topsort();
int ans=-1;
for(i=0;i<bcnt;i++)
{
ans=max(ans,num[i]);
}
// printf("%d\n",ans);
if(bcnt==ans) printf("Yes\n");
else printf("No\n");
}
return 0;
}
题意:若牛A崇拜牛B,牛B崇拜牛C,则牛A崇拜牛C,问总共有多少只牛受到其他所有牛的崇拜
分析:若有环存在,则该环里的所有牛都互相崇拜,则可将环看成是一个点,后再构图,若想存在某个 点的牛收到其他所有牛的崇拜,则该图必定是单链式图形(只有一个叶结点) tarjan缩点反向建图,然后只有一个入度为0
#include<stdio.h>
#include<string.h>
#include<vector>
#include<stack>
using namespace std;
const int MN=11000;
vector<int>SCC[MN];
vector<int>edge[MN];
stack<int>s;
int low[MN],dfn[MN];
int instack[MN],stap[MN];
int belong[MN];
int num[MN];
int ind[MN];
int sum[MN];
int tp,p;
int bcnt;
int n,m;
int cnt;
int pos;
void tarjan(int x)
{
low[x]=dfn[x]=++tp;
stap[++p]=x;
instack[x]=1;
for(int i=0;i<edge[x].size();i++)
{
int v=edge[x][i];
if(dfn[v]==-1)
{
tarjan(v);
if(low[x]>low[v])
low[x]=low[v];
}
else if(instack[v] && dfn[v]<low[x])
low[x]=dfn[v];
}
if(low[x]==dfn[x])
{
int top;
do
{
top=stap[p];
belong[top]=bcnt;
sum[bcnt]++;
instack[top]=0;
p--;
}while(x!=top);
bcnt++;
}
}
void topsort()
{
int u,v;
stack<int>s;
memset(num,0,sizeof(num));
for(int i=0;i<bcnt;i++)
{
if(ind[i]==0)
{
s.push(i);
pos=i;
cnt++;
}
}
}
int main()
{
int i,j;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(dfn,-1,sizeof(dfn));
memset(low,0,sizeof(low));
memset(instack,0,sizeof(instack));
memset(belong,0,sizeof(belong));
memset(ind,0,sizeof(ind));
memset(sum,0,sizeof(sum));
bcnt=tp=p=0;
for(i=1;i<=n;i++)
{
edge[i].clear();
SCC[i].clear();
}
for(i=0;i<m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
edge[a].push_back(b);
}
for(i=1;i<=n;i++)
{
if(dfn[i]==-1) tarjan(i);
}
for(i=1;i<=n;i++)
{
for(j=0;j<edge[i].size();j++)
{
int x=belong[i];
int y=belong[edge[i][j]];
if(x!=y)
{
SCC[y].push_back(x);
ind[x]++;
}
}
}
int ans=0;
cnt=0;
topsort();
if(cnt==1) printf("%d\n",sum[pos]);
else printf("0\n");
}
return 0;
}
POJ 2553 The Bottom of a Graph
题意:求出所有sink集合,sink集合的定义若v可达w,则w必定也可达v,求出所有的叶结点便可 而头节点不可以的原因是若v属于V,w不属于V,而v可达w,但是w不可达v,所以不可以 至于叶结点呢,v可达w,其中w必定都属于V集合
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
const int MN=5010;
vector<int>SCC[MN];
vector<int>edge[MN];
int low[MN],dfn[MN];
int instack[MN],stap[MN];
int belong[MN];
int num[MN];
int ind[MN];
int rem[MN];
int tp,p;
int bcnt;
int n,m;
int cas;
void tarjan(int x)
{
low[x]=dfn[x]=++tp;
stap[++p]=x;
instack[x]=1;
for(int i=0; i<edge[x].size(); i++)
{
int v=edge[x][i];
if(dfn[v]==-1)
{
tarjan(v);
if(low[x]>low[v])
low[x]=low[v];
}
else if(instack[v] && dfn[v]<low[x])
low[x]=dfn[v];
}
if(low[x]==dfn[x])
{
int top;
do
{
top=stap[p];
belong[top]=bcnt;
instack[top]=0;
p--;
}
while(x!=top);
bcnt++;
}
}
void topsort()
{
for(int i=0; i<bcnt; i++)
{
if(ind[i]==0)
{
for(int j=1; j<=n; j++)
{
if(belong[j]==i) rem[cas++]=j;
}
}
}
}
bool cmp(int a,int b)
{
return a<b;
}
int main()
{
int i,w,v,j;
while(scanf("%d",&n) && n)
{
scanf("%d",&m);
tp=p=bcnt=cas=0;
memset(dfn,-1,sizeof(dfn));
memset(low,0,sizeof(low));
memset(instack,0,sizeof(instack));
memset(belong,0,sizeof(belong));
memset(ind,0,sizeof(ind));
for(i=0; i<=n; i++)
{
edge[i].clear();
SCC[i].clear();
}
for(i=0; i<m; i++)
{
scanf("%d%d",&w,&v);
edge[w].push_back(v);
}
for(i=1; i<=n; i++)
{
if(dfn[i]==-1) tarjan(i);
}
for(i=1; i<=n; i++)
{
for(j=0; j<edge[i].size(); j++)
{
int x=belong[i];
int y=belong[edge[i][j]];
if(x!=y)
{
SCC[y].push_back(x);
ind[x]++;
}
}
}
topsort();
sort(rem,rem+cas,cmp);
printf("%d",rem[0]);
for(i=1; i<cas; i++)
{
printf(" %d",rem[i]);
}
printf("\n");
}
return 0;
}
题意: 找出割点,且将割点拿掉后,存在几个连通分量 分析: 构建一棵dfs树,序列dfn[i]为深度优先数,表示dfs时访问i节点的序号,low[i]表示从i节点出发能访问到的最小的深度优先数。 当且仅当节点u满足如下两个条件之一时,u为割点: 1.u为dfs树的根,且u至少有两个子节点。 2.u不是dfs树的根,至少存在一个节点v是u的子节点,且low[v]>=dfn[u]。 若u为割点,记subnets[u]为u的子节点数,则去掉u后,图被分成subnets[u]+1个部分(每个子节点的部分和u的祖先的部分),若u为dfs树的根,则分 成subnets[u]个部分(根节点没有祖先)。 以上全部算法均在dfs过程中完成。
割点模板
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MN=1111;
struct Edge
{
int to,next;
} edge[MN<<2];
int dfn[MN];
int low[MN];
int head[MN<<2];
int subnet[MN];
int E;
int tp;
int root;
int vis[MN];
void Init()
{
memset(dfn,-1,sizeof(dfn));
memset(low,0,sizeof(low));
memset(head,-1,sizeof(head));
memset(subnet,0,sizeof(subnet));
memset(vis,0,sizeof(vis));
E=tp=0;
}
void Add(int a,int b)
{
edge[E].to=b;
edge[E].next=head[a];
head[a]=E++;
}
void tarjan(int u,int fa){ //割点模板
int son=0;
vis[u]=1;
dfn[u]=low[u]=++tp;
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].to;
if(vis[v]==1 && v!=fa)
low[u]=min(low[u],dfn[v]);
if(!vis[v]){
tarjan(v,u);
son++;
low[u]=min(low[u],low[v]);
if((u==root && son>1) || (u!=root && dfn[u]<=low[v]))
subnet[u]++; //cut[u] 表示u这个点割边数
}
}
vis[u]=2;
}
int main()
{
int i,cas=1,n,a,b,nodes;
while(scanf("%d",&n) && n)
{
nodes=n;
Init();
scanf("%d",&b);
Add(n,b);
Add(b,n);
while(scanf("%d",&a) && a)
{
scanf("%d",&b);
if(nodes<a) nodes=a;
if(nodes<b) nodes=b;
Add(a,b);
Add(b,a);
}
for(i=1; i<=nodes; i++)
{
if(dfn[i]==-1)
{root=i;
tarjan(i,-1);
}
}
int flag=0;
printf("Network #%d\n",cas++);
for(i=1; i<=nodes; i++)
{
if(subnet[i]>=1)
{
flag=1;
printf(" SPF node %d leaves %d subnets\n",i,subnet[i]+1);
}
}
if(flag==0) printf(" No SPF nodes\n");
puts("");
}
return 0;
}