POJ2375 Cow Ski Area 【强连通分量】+【DFS】

大家好，又见面了，我是你们的朋友全栈君。

9 3
1 1 1 2 2 2 1 1 1
1 2 1 2 3 2 1 2 1
1 1 1 2 2 2 1 1 1

3

题意：本题描述了一片滑雪场，并且规定奶牛从一个点只能向它相邻的并且高度不大于它的点运动，现在想要在某些点对之间加上缆车使得奶牛也可以从较低点到达较高点，问最少需要多少辆这样的缆车就可以使得奶牛可以从任意一个点运动到滑雪场的每个角落。

题解：对于相邻的高度相同的点，实际上路线是双向的，所以它们构成了强连通，然后这道题可以找出所有强连通，于是就构成了一个DAG，然后答案就是max(入度为0的点，出度为0的点)，特别的，当整幅图已经是强连通时答案为0.这题求强连通可以用DFS，省去不少麻烦。

#include <stdio.h>
#include <string.h>
#define maxn 502

int map[maxn][maxn], scc[maxn][maxn];
int sccNum, id, head[maxn * maxn], n, m;
bool in[maxn * maxn], out[maxn * maxn];
struct Node{
    int to, next;
} E[maxn * maxn << 2];

void addEdge(int u, int v)
{
    E[id].to = v;
    E[id].next = head[u];
    head[u] = id++;
}

void getMap(int n, int m)
{
    int i, j; id = 0;
    for(i = 1; i <= n; ++i)
        for(j = 1; j <= m; ++j)
            scanf("%d", &map[i][j]);
}

void DFS(int x, int y)
{
    if(scc[x][y]) return;
    scc[x][y] = sccNum;    
    if(x + 1 <= n && map[x+1][y] == map[x][y]) DFS(x + 1, y);
    if(x - 1 >= 0 && map[x-1][y] == map[x][y]) DFS(x - 1, y);
    if(y + 1 <= m && map[x][y+1] == map[x][y]) DFS(x, y + 1);
    if(y - 1 >= 0 && map[x][y-1] == map[x][y]) DFS(x, y - 1);
}

void solve(int n, int m)
{
    memset(scc, 0, sizeof(scc));
    memset(in, 0, sizeof(in));
    memset(out, 0, sizeof(out));
    memset(head, -1, sizeof(head));
    sccNum = 0;
    int i, j, ans1 = 0, ans2 = 0;
    for(i = 1; i <= n; ++i)
        for(j = 1; j <= m; ++j)
            if(!scc[i][j]){
                ++sccNum; DFS(i, j);
            }
    for(i = 1; i <= n; ++i)
        for(j = 1; j <= m; ++j){
            if(i + 1 <= n && scc[i][j] != scc[i+1][j]){
                if(map[i][j] > map[i+1][j]){
                    addEdge(scc[i][j], scc[i+1][j]);
                    in[scc[i+1][j]] = out[scc[i][j]] = 1;
                } else{
                    addEdge(scc[i+1][j], scc[i][j]);
                    in[scc[i][j]] = out[scc[i+1][j]] = 1;
                }
            }
            if(j + 1 <= m && scc[i][j] != scc[i][j+1]){
                if(map[i][j] > map[i][j+1]){
                    addEdge(scc[i][j], scc[i][j+1]);
                    in[scc[i][j+1]] = out[scc[i][j]] = 1;
                } else{
                    addEdge(scc[i][j+1], scc[i][j]);
                    in[scc[i][j]] = out[scc[i][j+1]] = 1;
                }
            }
        }
    if(sccNum != 1)
        for(i = 1; i <= sccNum; ++i){
            if(!in[i]) ++ans1;
            if(!out[i]) ++ans2;
        }
    if(ans1 < ans2) ans1 = ans2;
    printf("%d\n", ans1);
}

int main()
{
    while(scanf("%d%d", &m, &n) == 2){
        getMap(n, m);
        solve(n, m);
    }
    return 0;
}