http://codeforces.com/gym/101257/problem/F
题意:给出一个n*m的地图,上面相同数字的代表一个国家,问对于每个国家有多少个国家在它内部(即被包围)。例如第一个样例,1包围2,2包围3,所以1包围2和3,2包围3。
思路:昨晚tmk大佬给我们讲了一下这题。对于一个国家,将和它相邻的国家连边,最后形成一个图。
可以发现,如果从随便一个点出发DFS,如果失去了某个点之后,导致整个图不连通了,那么这个点就一定包围了一些国家。
例如下面这个样例:
1 1 1 1 1 1
1 2 2 2 2 1
1 2 4 3 2 1
1 2 3 3 2 1
1 2 2 2 2 1
1 1 1 1 1 1
可以画出这张图,可以发现,如果失去了2这个点,将会导致1和3、4不连通,那么2必定是包围了一些点,但是不能确认到底是包围了3、4还是包围了1。
于是可以在最外层包围一层“新世界”,这样从新世界开始DFS,如果失去了像2这样的点导致图不连通了,那么2一定是包围了不在新世界一端的点。
0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 0
0 1 2 2 2 2 1 0
0 1 2 4 3 2 1 0
0 1 2 3 3 2 1 0
0 1 2 2 2 2 1 0
0 1 1 1 1 1 1 0
0 0 0 0 0 0 0 0
图变成这样了。
于是就可以使用tarjan来找割点,割点就包围了一些国家。一开始dfs一遍,维护一个sz代表子树的大小。然后如果该点是割点,就可以加上其子树的大小。
关于存边:tmk大佬们一开始的做法用了set判断重边,但是爆内存了。后来索性不管重边了,因为重边是不会影响找割点了(又不是找桥)。
如果自己来想肯定想不到QAQ。
#include <bits/stdc++.h>
using namespace std;
#define N 1000010
struct Edge {
int v, nxt;
} edge[N*];
int head[N], tot, sz[N], dfn[N], low[N], vis[N], ans[N], tid, mp[][], cnt; void Add(int u, int v) {
edge[tot] = (Edge) {v, head[u]}; head[u] = tot++;
edge[tot] = (Edge) {u, head[v]}; head[v] = tot++;
} void dfs(int u) {
sz[u] = ; if(cnt < u) cnt = u;
vis[u] = ;
for(int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].v;
if(vis[v]) continue;
dfs(v);
sz[u] += sz[v];
}
} void tarjan(int u, int fa) {
dfn[u] = low[u] = ++tid;
vis[u] = ;
for(int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].v;
if(fa == v) continue;
if(!dfn[v]) {
tarjan(v, u);
low[u] = min(low[u], low[v]);
if(low[v] >= dfn[u]) ans[u] += sz[v];
} else if(vis[v]) {
low[u] = min(low[u], dfn[v]);
}
}
} int main() {
int n, m;
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i++) for(int j = ; j <= m; j++) scanf("%d", &mp[i][j]);
memset(head, -, sizeof(head));
for(int i = ; i <= n; i++) {
for(int j = ; j <= m; j++) {
if(mp[i][j] != mp[i+][j]) Add(mp[i][j], mp[i+][j]);
if(mp[i][j] != mp[i][j+]) Add(mp[i][j], mp[i][j+]);
}
}
dfs();
memset(vis, , sizeof(vis));
tarjan(, -);
for(int i = ; i <= cnt; i++) printf("%d ", ans[i]);
return ;
}