POJ 1236 Network of Schools(强连通+缩点)

缩点

缩点就是要将两两之间可以相互到达的点，缩成一个点来表示（即求无向图的连通分量，或者有向图的强连通分量），他们的求法都是相同的，都是将无向图转化为有向图。

Trajan算法求缩点

stack\ st;

int num;///num:强连通分量(连通块)的个数,缩点后点的个数

bool vis[105];///该点是否访问过

int inst[105];///该点是否在栈中

int time[105];///i点第一次被访问的时间

int low[105];///i点所在强连通分量子图中第一个被搜到的点的time值

int ltt[105];///i点属于第几个强连通分量(0表示不属于任何一个)

强连通分量内元素个数最少为1(该元素本身),这意味着每个元素都有从属的强连通分量

Code(Trajan)

void Trajan(int x)///搜索x点及其子树
{
    int temp;
    st.push(x);
    inst[x] = vis[x] = 1;
    low[x] = time[x] = ++t;
    for(int i = 0; i < v[x].size(); i++)
    {
        temp = v[x][i];
        if(vis[temp] == 0)
        {
            Trajan(temp);
            low[x] = min(low[x], low[temp]);
        }
        else if(inst[temp] == 1)///成环时
            low[x] = min(low[x], time[temp]);
        else///点temp访问过却不在当前栈里：属于已发现的强连通分量
            continue;///这两个不能合二为一的原因：只有从此指彼的单向路
    }
    if(low[x] == time[x])
    {
        num++;///找到第num个强连通分量
        while(!st.empty())
        {
            temp = st.top();
            st.pop();
            ltt[temp] = num;///temp结点属于第num个强连通分量
            inst[temp] = 0;
            if(temp == x)
                break;
        }
    }
}

POJ 1236

n所学校，它们通过单向边连接，如果A—>B表示A学校可以传递信息给B学校

问题一：至少要向几个学校传递信息，才能保证所有学校都能收到信息；

问题二：至少要添加多少组关系，才能保证给任意一个学校原始信息后，其他所有学校都能收到信息

Analyze

问题一：缩点后数出入度为0的点的个数

问题二：缩点后求再次完成强连通最少添加几条边max(ain, aout)

Code

#include <stack>
#include <vector>
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;

stack<int> st;
vector<int> v[105], nv[105];
int n, t, num;///num:强连通分量(连通块)的个数,缩点后点的个数
int ain, aout;

bool vis[105];///该点是否访问过
int inst[105];///该点是否在栈中

int time[105];///i点第一次被访问的时间
int low[105];///i点所在强连通分量子图中第一个被搜到的点的time值

int ltt[105];///i点属于第几个强连通分量(0表示不属于任何一个)
int in[105], out[105];

void Trajan(int x)///搜索x点及其子树
{
    int temp;
    st.push(x);
    inst[x] = vis[x] = 1;
    low[x] = time[x] = ++t;
    for(int i = 0; i < v[x].size(); i++)
    {
        temp = v[x][i];
        if(vis[temp] == 0)
        {
            Trajan(temp);
            low[x] = min(low[x], low[temp]);
        }
        else if(inst[temp] == 1)///成环时
            low[x] = min(low[x], time[temp]);
        else///点temp访问过却不在当前栈里：属于已发现的强连通分量
            continue;///这两个不能合二为一的原因：只有从此指彼的单向路
    }
    if(low[x] == time[x])
    {
        num++;///找到第num个强连通分量
        while(!st.empty())
        {
            temp = st.top();
            st.pop();
            ltt[temp] = num;///temp结点属于第num个强连通分量
            inst[temp] = 0;
            if(temp == x)
                break;
        }
    }
}

///强连通分量内元素个数最少为1(该元素本身)
///这意味着每个元素都有从属的强连通分量

int main()
{
    int x, temp;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        while(scanf("%d", &x), x != 0)
            v[i].push_back(x);
    }

    t = num = 0;
    for(int i = 1; i <= n; i++)
        if(vis[i] == 0)
            Trajan(i);

    for(int i = 1; i <= n; i++)
        for(int j = 0; j < v[i].size(); j++)
        {
            temp = v[i][j];
            if(ltt[i] != ltt[temp])
                nv[ltt[i]].push_back(ltt[temp]);
        }

    for(int i = 1; i <= num; i++)
        for(int j = 0; j < nv[i].size(); j++)
            in[nv[i][j]]++, out[i]++;

    ain = aout = 0;
    for(int i = 1; i <= num; i++)
    {
        if(in[i] == 0)
            ain++;
        if(out[i] == 0)
            aout++;
    }

    printf("%d\n", ain);
    if(num == 1)
        printf("0\n");
    else
        printf("%d\n", max(ain, aout));
        ///让所有缩点形成一个强连通图
        ///假设 aout = max(ain, aout)
        ///那么恰当选择(aout - 1)个出度为0的点逆向添边会减少缩点，最终形成一条单向链
        ///此时按照链的方向添一条连接首尾的边就形成强连通图(一个标准有向环)
    return 0;
}

参考1： https://blog.csdn.net/jaihk662/article/details/52194288

参考2： https://blog.csdn.net/nhl19961226/article/details/79114287

Kosaraju求缩点

将边反向建立后，强连通分量内的点，其可达性不受影响。

但不能沿着边访问到除了这个强连通分量之外的点

#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_V = 10005;

int V, ain, aout, in[MAX_V], out[MAX_V];
vector<int> vs;
vector<int> G[MAX_V];
vector<int> rG[MAX_V];
vector<int> nv[MAX_V];

bool used[MAX_V];
int cmp[MAX_V];

void add_eage(int from, int to)
{
    G[from].push_back(to);
    rG[to].push_back(from);
}

void DFS(int v)
{
    used[v] = 1;
    for(int i = 0; i < G[v].size(); ++i)
        if(!used[ G[v][i] ])
            DFS(G[v][i]);
    vs.push_back(v);
}

void rDFS(int v, int k)
{
    used[v] = 1;
    cmp[v] = k;
    for(int i = 0; i < rG[v].size(); ++i)
        if(!used[ rG[v][i] ])
            rDFS(rG[v][i], k);
}

int scc()
{
    memset(used, 0, sizeof(used));
    vs.clear();
    for(int v = 1; v <= V; ++v)
        if(!used[v])
            DFS(v);
    memset(used, 0, sizeof(used));
    int k = 0;
    for(int i = vs.size() - 1; i >= 0; --i)
        if(!used[vs[i]])
            rDFS(vs[i], ++k);
    return k;
}

int main()
{
    int x, temp;
    scanf("%d", &V);
    for(int i = 1; i <= V; i++)
    {
        while(scanf("%d", &x), x != 0)
            add_eage(i, x);
    }

    int num = scc();

    for(int i = 1; i <= V; i++)
        for(int j = 0; j < G[i].size(); j++)
        {
            temp = G[i][j];
            if(cmp[i] != cmp[temp])
                nv[cmp[i]].push_back(cmp[temp]);
        }

    for(int i = 1; i <= num; i++)
        for(int j = 0; j < nv[i].size(); j++)
            in[nv[i][j]]++, out[i]++;

    ain = aout = 0;
    for(int i = 1; i <= num; i++)
    {
        if(in[i] == 0)
            ain++;
        if(out[i] == 0)
            aout++;
    }

    printf("%d\n", ain);
    if(num == 1)
        printf("0\n");
    else
        printf("%d\n", max(ain, aout));
    return 0;
}