hihoCoder 1184-连通性二·边的双连通分量
#1184 : 连通性二·边的双连通分量
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
在基本的网络搭建完成后，学校为了方便管理还需要对所有的服务器进行编组，网络所的老师找到了小Hi和小Ho，希望他俩帮忙。
老师告诉小Hi和小Ho：根据现在网络的情况，我们要将服务器进行分组，对于同一个组的服务器，应当满足：当组内任意一个连接断开之后，不会影响组内服务器的连通性。在满足以上条件下，每个组内的服务器数量越多越好。
比如下面这个例子，一共有6个服务器和7条连接：
其中包含2个组，分别为{1,2,3},{4,5,6}。对{1,2,3}而言，当1-2断开后，仍然有1-3-2可以连接1和2；当2-3断开后，仍然有2-1-3可以连接2和3；当1-3断开后，仍然有1-2-3可以连接1和3。{4,5,6}这组也是一样。
老师把整个网络的情况告诉了小Hi和小Ho，小Hi和小Ho要计算出每一台服务器的分组信息。
提示：边的双连通分量
输入
第1行：2个正整数，N,M。表示点的数量N，边的数量M。1≤N≤20,000, 1≤M≤100,000
第2..M+1行：2个正整数，u,v。表示存在一条边(u,v)，连接了u,v两台服务器。1≤u<v≤N
保证输入所有点之间至少有一条连通路径。
输出
第1行：1个整数，表示该网络的服务器组数。
第2行：N个整数，第i个数表示第i个服务器所属组内，编号最小的服务器的编号。比如分为{1,2,3},{4,5,6}，则输出{1,1,1,4,4,4}；若分为{1,4,5},{2,3,6}则输出{1,2,2,1,1,2}
样例输入
6 7
1 2
1 3
2 3
3 4
4 5
4 6
5 6
样例输出
2
1 1 1 4 4 4
边的双连通分量是指无向图的一个子图，当删除其中任意一条边后，不改变图内点的连通性。在hihoCoder week 52-1-连通性·一中，我们求过一个图的桥，当删除所有桥之后，图肯定不连通了，此时剩下的每一个区域就是我们要求的边的双连通分量。 所以简单的方法就是先用上一题的方法求出桥，然后删除所有桥，进行DFS遍历求出边的双连通分量。但是提示给出了一个更巧妙的方法，在求桥的过程中，使用一个堆栈保存遍历过的点，当low[u]==dfn[u]时，u点通过回边追溯到的最早节点是其本身，说明u和parent[u]的同伙只有唯一的一条边(parent[u],u)相连，且这条边是桥，那么此时栈内在u之前入栈的点和u被该桥分割开，也就是说从u到栈顶的所有元素是一组。 完整代码如下： [cpp] #include<iostream> #include<cstdio> #include<stack> #include<algorithm> #include<vector> using namespace std; const int kMaxN = 20005; int n, m; vector<vector<int>> graph; stack<int> stk; int visit[kMaxN]; int dfn[kMaxN]; int low[kMaxN]; int parent[kMaxN]; int belong[kMaxN]; int bridge_num=0; void dfs(int u) { //记录dfs遍历次序 static int counter = 0; //记录节点u的子树数 int children = 0; visit[u] = 1; //初始化dfn与low dfn[u] = low[u] = ++counter; //将u加入栈 stk.push(u); for (int i = 0; i < graph[u].size(); i++) { int v = graph[u][i]; //节点v未被访问，则(u,v)为树边 if (visit[v] == 0) { children++; parent[v] = u; dfs(v); low[u] = min(low[u], low[v]); //bridge if (low[v] > dfn[u]) { bridge_num++; } } //节点v已访问，则(u,v)为回边 else if (v != parent[u]) { low[u] = min(low[u], dfn[v]); } } if (low[u] == dfn[u]) { int min_id = u; vector<int> member; while (stk.top() != u) { min_id = min(min_id, stk.top()); member.push_back(stk.top()); stk.pop(); } member.push_back(u); stk.pop(); for (int i = 0; i < member.size(); i++) belong[member[i]] = min_id; } } int main() { //freopen("input.txt", "r",stdin); scanf("%d %d", &n, &m); graph.resize(n + 1); int u, v; while (m–) { scanf("%d %d", &u, &v); graph[u].push_back(v); graph[v].push_back(u); } dfs(1); printf("%dn", bridge_num+1); for (int i = 1; i <= n; i++) printf("%d ", belong[i]); return 0; } [/cpp] 本代码提交AC，用时69MS，内存5MB。 有一点需要提醒，题目要求同一个联通分量用内部最小结点来表示，这里不能想当然的认为当low[u]=dfn[u]时，最小节点是u，万一是下图，2和3比6后进入堆栈，也就是2和3在堆栈中的位置在6的上面，当回溯到6号节点时，有low[6]==dfn[6]，但是右边的联通分量中最小节点显然是2，所以还是老老实实遍历求最小值。
]]>