NC51269 Network of Schools

题目：

给你一张有向图，问最少要加几条边才能使得图上的点都属于同一个强连通分量

题解：

在这里插入图片描述
加边变成强连通分量
在这里插入图片描述

缩点之后，入度为0的点和出度为0的点两两连边，多随便一连——答案就是max（入度为0的点数，出度为0的点数）
在这里插入图片描述
处理后：
在这里插入图片描述

代码：

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);
   return s*w;
}
const int maxn=1e6+9;
vector<int>edge[maxn];
int low[maxn],dfn[maxn];
int vis[maxn];
int cnt=0;
stack<int>s;
int num1,num2;
int block; 
int color[maxn];
int in[maxn],out[maxn];
void tarjan(int u)
{
    low[u]=dfn[u]=++cnt;
    vis[u]=1;
    s.push(u);
    for(int i=0;i<edge[u].size();i++)
    {
        int v=edge[u][i];
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(vis[v])low[u]=min(low[u],dfn[v]);
    }
    int x;
    if(dfn[u]==low[u])
    {
        block++;
        do
        {
            x=s.top();
            s.pop();
            vis[x]=0;
            color[x]=block;
        }while(x!=u);
    } 
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        while(cin>>x)
        {
            if(x==0)break;
            edge[i].push_back(x);
        }

    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])tarjan(i);
    }
    for(int u=1;u<=n;u++)
    {
        for(int i=0;i<edge[u].size();i++)
        {
            int x=color[u];
            int y=color[edge[u][i]];
            if(x!=y)
            {
                out[x]++;
                in[y]++;
            }
        }
    }
    for(int i=1;i<=block;i++)
    {
        if(in[i]==0)num1++;
        if(out[i]==0)num2++;
    }
    if(block==1)cout<<"1"<<endl<<"0"<<endl;
    else printf("%d\n%d",num1,max(num1,num2));
}