poj 1236 Network of Schools （强连通分量+缩点）

题目大概：

每个学校都可以把软件复制好，交给它名单上的学校。

问题A：把软件复制成几份，然后交给不同的学校，所有学校才能够都有软件。

问题B：添加几条边，能使得这个图变成强连通图。

思路：

找出所有的强连通分量，然后缩点，变成一个新有向无环图，求每个强连通分量的入度和出度。

A：入度是0的点就是复制的最小数量，因为只要给强连通分量一个软件，他就会传到每个点，所以找出没有入口的强连通分量的数量就是要复制的数量（其他强连通分量都可以由这些分量传递过去）。

B：in0为入度为0点的数量，out0出度为0的点的数量，添加的边的数量是=max（in0，out0）；这个不好证明，但画一下图，自己理解一下，也是很容易理解的。

KO:

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

#define ll long long

#define pb push_back

#define mem(a,b) memset(a,b,sizeof(a))

const int N=;

vector<int>g[N];

vector<int>rg[N];

vector<int>vs;

bool vis[N];

int cmp[N];

int in[N]={};

int out[N]={};

int n,a;

void add_edge(int u,int v)

{

    g[u].pb(v);

    rg[v].pb(u);

}

void dfs(int u)

{

    vis[u]=true;

    for(int i=;i<g[u].size();i++)if(!vis[g[u][i]])dfs(g[u][i]);

    vs.pb(u);

}

void rdfs(int u,int k)

{

    vis[u]=true;

    cmp[u]=k;

    for(int i=;i<rg[u].size();i++)if(!vis[rg[u][i]])rdfs(rg[u][i],k);

}

int scc()

{

    mem(vis,false);

    vs.clear();

    for(int i=;i<=n;i++)if(!vis[i])dfs(i);

    mem(vis,false);

    int k=;

    for(int i=vs.size()-;i>=;i--)if(!vis[vs[i]])rdfs(vs[i],k++);

    return k;

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    cin>>n;

    for(int i=;i<=n;i++)

    {

        while(cin>>a&&a)add_edge(i,a);

    }

    int t=scc();

    for(int i=;i<=n;i++)

    {

        for(int j=;j<g[i].size();j++)

        if(cmp[i]!=cmp[g[i][j]])out[cmp[i]]++,in[cmp[g[i][j]]]++;

    }

    int in1=,out1=;

    for(int i=;i<t;i++)

    {

        //cout<<in[i]<<' '<<out[i]<<endl;

        if(in[i]==)in1++;

        if(out[i]==)out1++;

    }

    cout<<in1<<endl;

    if(t==)cout<<<<endl;

    else cout<<max(in1,out1)<<endl;

    return ;

}

TA:

#include<iostream>

#include<cstdio>

#include<cstring>

#include<vector>

using namespace std;

const int maxn =  + ;

int N;

int In[maxn], Out[maxn];

/***************************Tarjan算法模板***************************/

vector<int> G[maxn];

int Mark[maxn], Root[maxn], Stack[maxn];                                //时间戳，根(当前分量中时间戳最小的节点)，栈

bool Instack[maxn];                                                     //是否在栈中标记

int Ssc[maxn];                                                          //每个节点所在的强连通分量的编号

int Index, Ssc_n, Top;                                                  //搜索时用的时间戳，强连通分量总数，栈顶指针

void Tarjan(int u)                                                      //u 当前搜索到的点

{

    Mark[u] = Root[u] = ++ Index;                                       //每找到一个点，对时间戳和根初始化

    Stack[Top ++] = u;                                                  //压栈

    Instack[u] = true;                                                  //在栈中标记

    int v;

    for(int i= ; i< G[u].size(); i++)                                  //向下搜索

    {

        v = G[u][i];

        if(Mark[v] == )                                                //没到过的点

        {

            Tarjan(v);                                                  //先向下搜索

            if(Root[u] > Root[v]) Root[u] = Root[v];                    //更新根

        }

        else if(Instack[v] && Root[u] > Mark[v]) Root[u] = Mark[v];     //到过的点且点仍在栈中，试着看这个点能不能成为根

    }

/*对当前点的搜索结束*/

    if(Mark[u] == Root[u])                                              //当前点本身时根

    {

        Ssc_n ++;                                                       //更新强连通分量数

        do{                                                             //栈中比它后入栈的元素在以它为根的强连通分量中

            v = Stack[-- Top];

            Instack[v] = false;

            Ssc[v] = Ssc_n;

        }while(v != u);                                                 //直到它自己

    }

}

void SSC()

{

    memset(Mark, , sizeof Mark);                                       //初始化时间戳和栈内标记

    memset(Instack, false, sizeof Instack);

    Index = Ssc_n = Top = ;                                            //初始化时间戳，强连通分量数，栈顶指针

    for(int i= ; i<= N; i++)                                           //保证图上所有点都访问到

        if(Mark[i] == ) Tarjan(i);

}

/***************************Tarjan算法模板***************************/

int main()

{

    //freopen("in.txt", "r", stdin);

    scanf("%d", &N);

    for(int i= ; i<= N; i++)

    {

        int x;

        while(scanf("%d", &x), x)

            G[i].push_back(x);

    }

    SSC();

    if(Ssc_n == )                                                      //只有一个强连通分量的情况

    {

        cout << "1\n0\n";

        return ;

    }

    memset(In, , sizeof In);                                           //求每个强连通分量的入度和出度

    memset(Out, , sizeof Out);

    for(int u= ; u<= N; u++)

    {

        for(int i= ; i< G[u].size(); i++)

        {

            int v = G[u][i];

            if(Ssc[u] != Ssc[v])

                Out[Ssc[u]] ++, In[Ssc[v]] ++;

        }

    }

    int S1 = , S2 = ;                                                 //找入度为0、出度为0的点的数目

    for(int i= ; i<= Ssc_n; i++)

    {

        if(In[i] == ) S1 ++;

        if(Out[i] == ) S2 ++;

    }

    cout << S1 << endl << max(S1, S2) << endl;

    return ;

}