首页 > 代码库 > Codeforces Gym101257F：Islands II（求割点+思维）
Codeforces Gym101257F：Islands II（求割点+思维）
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。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define N 1000010 4 struct Edge { 5 int v, nxt; 6 } edge[N*8]; 7 int head[N], tot, sz[N], dfn[N], low[N], vis[N], ans[N], tid, mp[1010][1010], cnt; 8 9 void Add(int u, int v) {10 edge[tot] = (Edge) {v, head[u]}; head[u] = tot++;11 edge[tot] = (Edge) {u, head[v]}; head[v] = tot++;12 }13 14 void dfs(int u) {15 sz[u] = 1; if(cnt < u) cnt = u;16 vis[u] = 1;17 for(int i = head[u]; ~i; i = edge[i].nxt) {18 int v = edge[i].v;19 if(vis[v]) continue;20 dfs(v);21 sz[u] += sz[v];22 }23 }24 25 void tarjan(int u, int fa) {26 dfn[u] = low[u] = ++tid;27 vis[u] = 1;28 for(int i = head[u]; ~i; i = edge[i].nxt) {29 int v = edge[i].v;30 if(fa == v) continue;31 if(!dfn[v]) {32 tarjan(v, u);33 low[u] = min(low[u], low[v]);34 if(low[v] >= dfn[u]) ans[u] += sz[v];35 } else if(vis[v]) {36 low[u] = min(low[u], dfn[v]);37 }38 }39 }40 41 int main() {42 int n, m;43 scanf("%d%d", &n, &m);44 for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) scanf("%d", &mp[i][j]);45 memset(head, -1, sizeof(head));46 for(int i = 0; i <= n; i++) {47 for(int j = 0; j <= m; j++) {48 if(mp[i][j] != mp[i+1][j]) Add(mp[i][j], mp[i+1][j]);49 if(mp[i][j] != mp[i][j+1]) Add(mp[i][j], mp[i][j+1]);50 }51 }52 dfs(0);53 memset(vis, 0, sizeof(vis));54 tarjan(0, -1);55 for(int i = 1; i <= cnt; i++) printf("%d ", ans[i]);56 return 0;57 }
Codeforces Gym101257F：Islands II（求割点+思维）