首页 > 代码库 > BZOJ1051

BZOJ1051

2024-08-19 21:35:37   218人阅读

强连通。

若只存在一个强连通分量出度为0（树根，万人敬仰），答案就是这个强连通的节点数。

若存在多个，答案即为0

#include<cstdio>
#include<cstdlib>
#include<cstring>
#define min(x,y) (x<y?x:y)
struct mod{int x,y,next;};
mod q[50015];
int len=0,id=0,tp=0,num=0;
int first[10015];
int dfn[10015];
int low[10015];
int home[10015];
int size[10015];
bool vis[10015];
int sta[10015];
int in[10015];
int out[10015];
void ins(int x,int y)
{
 len++;
 q[len].x=x;
 q[len].y=y;
 q[len].next=first[x];
 first[x]=len;
}
void dfs(int x)
{
 dfn[x]=low[x]=++id;
 vis[x]=true;
 sta[++tp]=x;
 for (int i=first[x];i!=0;i=q[i].next)
 {
  int y=q[i].y;
  if (dfn[y]==-1)
  {
   dfs(y);
   low[x]=min(low[x],low[y]);
  }
  else
  {
   if (vis[y]==true)
   low[x]=min(low[x],dfn[y]);  
  }
 }
 if (low[x]==dfn[x])
 {
  num++;
  while(1)
  {
   int i=sta[tp--];
   vis[i]=false;
   home[i]=num;
   size[num]++;
   if (i==x)break;
  }
 }
}
int main()
{
 int n,m;
 scanf("%d%d",&n,&m);
 for (int i=1;i<=m;i++) 
 {
  int x,y;
  scanf("%d%d",&x,&y);
  ins(x,y);
 }
 memset(dfn,-1,sizeof(dfn));
 memset(low,0,sizeof(low));
 memset(size,0,sizeof(size));
 for (int i=1;i<=n;i++)
 if (dfn[i]==-1)
 dfs(i);
 int ans=0;
 for (int i=1;i<=m;i++)
 {
  if (home[q[i].x]!=home[q[i].y])
  in[home[q[i].y]]++,out[home[q[i].x]]++;
 }
 for (int i=1;i<=num;i++)
 {
  if (out[i]==0&&in[i]!=0)
  ans+=size[i];
 }
 printf("%d\n",ans);
}

BZOJ1051


联系
我们