http://codeforces.com/gym/103049
J. Joint Excavation
题意:给定一张连通的无向图,要求给出一条链,把链从图上去掉,把图切成若干个连通块,给每个连通块分配颜色 1 或 2,要求两种颜色的点数相同。给出链以及颜色划分。
dfs
很妙的dfs题。
下面称颜色 1 的点集为 A,颜色 2 的点集为 B,链的点集为 C。
初始把所有点分到点集 A。
任选一点开始dfs,遇到之前没有访问过的点则把该点从 A 去掉,分到点集 C,即链上。
当对一个节点的访问结束后,把该点再从点集 C 中去掉,分到点集 B。
期间检查当 A,B 大小相同时exit。
可以发现这三个点集分别对应dfs中的不同状态:A 表示为访问状态,B 表示访问结束,C 表示正在访问。
dfs中访问结束的点必定不会与未访问的点相邻,否则一定会先去访问那个未被访问的点。
而正在访问的点也一定是一条链,这也正是深度优先搜索的特性。
访问结束的点是可能与多个正在访问的点相邻的,但这些正在访问的点一定构成一条链。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
| #include <bits/stdc++.h> #define rep(i, l, r) for (int i = l, i##end = r; i <= i##end; ++i) #define repo(i, l, r) for (int i = l, i##end = r; i < i##end; ++i) #define per(i, l, r) for (int i = l, i##end = r; i >= i##end; --i) bool dbg = true; #define debug(x) if (dbg) cout << #x << ":\t" << (x) << endl; #define here if (dbg) printf("Passing [%s] in Line %d\n", __FUNCTION__, __LINE__); using namespace std; typedef long long LL; typedef long long ll; typedef pair<int, int> Pair;
const int maxn = 2e5+5, inf = 0x3f3f3f3f, INF = inf; const int N = maxn; const int minn = 1e3;
int n, m; vector<int>G[N],vc; int ca, cb, c[N]; void ck(){ if(ca == cb){ printf("%d %d\n", n-ca-cb, ca); for(int u:vc)printf("%d ",u);puts(""); for(int i=1;i<=n;i++)if(c[i]==0)printf("%d ", i);puts(""); for(int i=1;i<=n;i++)if(c[i]==1)printf("%d ", i);puts(""); exit(0); } } void dfs(int u, int _fa){ ck(); if(c[u])return; ca--; c[u]=2; vc.push_back(u); for(int v:G[u]){ if(v==_fa)continue; dfs(v, u); } ck(); vc.pop_back(); cb++; c[u]=1; ck(); } int main(){ scanf("%d%d", &n,&m); for(int i=1;i<=m;i++){ int u,v; scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u); } ca = n; dfs(1, 0); return 0; }
|