题解 P2812 【校园网络】

herofox · 2017-10-25 14:40:34 · 题解

看到楼下都是Tarjan，来一发Kosaraju算法的解法

算法思路：先对原图dfs，再对反图dfs，如果两次从A都能遍历到B，说明A和B在同一个强连通分量中

优化：在第一次遍历时记录离开每一个点的时间，第二次遍历时每次从第一次遍历离开最晚且还没有在第二次遍历中访问的点开始

求出各个强连通分量后的步骤就和楼下各位的相同了

代码如下：

[codec]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
using namespace std;
#define Fill_0(x) memset(x, 0, sizeof x)
const int maxn = 10000 + 1000;
const int maxm = 1000000 + 1000;
int n, u[maxm], v[maxm], m;
int dfn[maxn], DFN = 0;
int color[maxn], tot = 0;
vector<int> g[maxn];
bool vis[maxn], section = 0;
int In[maxn], Out[maxn], inz = 0, outz = 0;
inline void Insert()
{
    for(int i = 1;i <= n;++i)
        g[i].clear();
    for(int i = 1;i <= m;++i)
        g[u[i]].push_back(v[i]);
}
inline void dfs(int p)
{
    vis[p] = 1;
    int s = g[p].size();
    for(int i = 0;i <= s - 1;++i)
        if(!vis[g[p][i]])
            dfs(g[p][i]);
    if(section == 0)
        dfn[++DFN] = p;
    else
        color[p] = DFN;
}
int main()
{
    scanf("%d", &n);
    for(int i = 1;i <= n;++i)
    {
        int x;
        scanf("%d", &x);
        while(x != 0)
            u[++m] = i, v[m] = x, scanf("%d", &x), g[v[m]].push_back(u[m]);
    }
    for(int i = 1;i <= n;++i)
        if(!vis[i])
            dfs(i);
    Fill_0(vis);
    DFN = 0;
    section = 1;
    Insert();
    for(int i = n;i >= 1;--i)
        if(!vis[dfn[i]])
        {
            ++DFN;
            dfs(dfn[i]);
        }
    for(int i = 1;i <= m;++i)
        if(color[u[i]] != color[v[i]])
            ++In[color[v[i]]], ++Out[color[u[i]]];
    for(int i = 1;i <= DFN;++i)
    {
        if(In[i] == 0)
            ++inz;
        if(Out[i] == 0)
            ++outz;
    }
    printf("%d\n%d\n", inz, max(outz, inz));
}
[/codec]