首页 > 代码库 > hihocoder #1190 : 连通性·四 点双联通分量
hihocoder #1190 : 连通性·四 点双联通分量
http://hihocoder.com/problemset/problem/1190?sid=1051696
先抄袭一下
描述
小Hi和小Ho从约翰家回到学校时，网络所的老师又找到了小Hi和小Ho。
老师告诉小Hi和小Ho：之前的分组出了点问题，当服务器(上次是连接)发生宕机的时候，在同一组的服务器有可能连接不上，所以他们希望重新进行一次分组。这一次老师希望对连接进行分组，并把一个组内的所有连接关联的服务器也视为这个组内的服务器(注意一个服务器可能属于多个组)。
这一次的条件是对于同一个组满足：当组内任意一个服务器宕机之后，不会影响组内其他服务器的连通性。在满足以上条件下，每个组内的边数量越多越好。
比如下面这个例子，一共有6个服务器和7条连接：
其中包含3个组，分别为{(1,2),(2,3),(3,1)},{(4,5),(5,6),(4,6)},{(3,4)}。对{(1,2),(2,3),(3,1)}而言，和该组边相关联的有{1,2,3}三个服务器：当1宕机后，仍然有2-3可以连接2和3；当2宕机后，仍然有1-3可以连接1和3；当3宕机后，仍然有1-2可以连接1和2。
老师把整个网络的情况告诉了小Hi和小Ho，希望小Hi和小Ho统计一下一共有多少个分组。
提示：点的双连通分量
输入
第1行：2个正整数，N,M。表示点的数量N，边的数量M。1≤N≤20,000, 1≤M≤100,000
第2..M+1行：2个正整数，u,v。第i+1行表示存在一条边(u,v)，编号为i，连接了u,v两台服务器。1≤u<v≤N
保证输入所有点之间至少有一条连通路径。
输出
第1行：1个整数，表示该网络的连接组数。
第2行：M个整数，第i个数表示第i条连接所属组内，编号最小的连接的编号。比如分为{(1,2)[1],(2,3)[3],(3,1)[2]},{(4,5)[5],(5,6)[7],(4,6)[6]},{(3,4)[4]}，方括号内表示编号，则输出{1,1,1,4,5,5,5}。
- 样例输入
-
6 7 1 2 1 3 2 3 3 4 4 5 4 6 5 6
- 样例输出
-
3 1 1 1 4 5 5 5
提示：点的双连通分量
小Ho：那么我们这一次求的和前一次有什么区别？
小Hi：在上一次中，我们求解的是边的双连通分量，而我们这一次叫做点的双连通分量，其定义为：
对于一个无向图的子图，当删除其中任意一个点后，不改变图内点的连通性，这样的子图叫做点的双连通子图。而当子图的边数达到最大时，叫做点的双连通分量。
小Ho：那和上一次有什么不同么？
小Hi：与前一次的区别在于，可能出现下面这种情况时：
存在两个分组，分别是{(1,2),(2,3),(3,1)},{(3,4),(4,5),(3,5)}。其不能分成一组是因为当3号服务器宕机之后，1,2与4,5便不再连通。
小Ho：感觉好像难了很多？
小Hi：其实也还好啦，这一次的话只需要稍作一下改进就好。
首先我们从上面的例子可以猜到，桥一定是作为一个单独的点的双连通分量。而被桥分割的区域，可能出现两种情况：
第一种情况下，桥两边都各是一个连通分量，那么桥的存在把整个图分成了3个连通分量，桥本身作为一个点的双连通分量，而A,B两个分量还无法判定。在这图中，A,B两点本质都是割点。
第二种情况下，桥一边是连通分量，而另一边是独立的点。桥的存在把整个图分成了2个连通分量，B点部分因为没有边，所以不构成一个组。在这图中，只有A点是割点。
那么我们可以先根据桥，把整个图先分割开来。
在点的双连通分量分量中出现了一种特殊的情况，而产生这种情况是因为在一个边的双连通分量中存在了割点。那么在去掉桥的每一个连通分量中，我们需要再找出割点。
小Ho：简单每存在一个桥就分割一次图，每个连通分量中存在一个割点就分割一次图。
小Hi：是这样的，但其实还可以更近一步考虑，对于桥的两种情况，它分割个区域数刚好就等于割点数+1；而连通分量内的割点同样也是，每存在一个割点，点的双连通分量就增加一个。
小Ho：这样说来，只要统计割点数量，点的双连通分量就等于割点数量加1咯？
小Hi：没错，每存在一个割点，就把一个区域一分为二，所以最后的结果也就是统计割点的数量就可以了。而对于分组具体情况，我们仍然采用栈来辅助我们记录，代码如下：
void dfs(int u) {
//记录dfs遍历次序
static int counter = 0;
//记录节点u的子树数
int children = 0;
ArcNode *p = graph[u].firstArc;
visit[u] = 1;
//初始化dfn与low
dfn[u] = low[u] = ++counter;
for(; p != NULL; p = p->next) {
int v = p->adjvex;
if(edge(u,v)已经被标记) continue;
//节点v未被访问，则(u,v)为树边
if(!visit[v]) {
children++;
parent[v] = u;
edgeStack[top++] = edge(u,v); // 将边入栈
dfs(v);
low[u] = min(low[u], low[v]);
//case (1)
if(parent[u] == NIL && children > 1) {
printf("articulation point: %d\n", u);
// mark edge
// 将边出栈，直到当前边出栈为止，这些边标记为同一个组
do {
nowEdge = edgeStack[top];
top--;
// 标记nowEdge
} while (nowEdge != edge(u,v))
}
//case (2)
if(parent[u] != NIL && low[v] >= dfn[u]) {
printf("articulation point: %d\n", u);
// mark edge
// 将边出栈，直到当前边出栈为止，这些边标记为同一个组
do {
nowEdge = edgeStack[top];
top--;
// 标记nowEdge
} while (nowEdge != edge(u,v))
}
}
//节点v已访问，则(u,v)为回边
else if(v != parent[u]) {
edgeStack[top++] = edge(u,v);
low[u] = min(low[u], dfn[v]);
}
}
}
关于点的双联通分量
搞了我很久。现在发现其实对边进行分块。以前的有向图强联通分量和边双联通分量，那些都是对点进行分块。
现在需要对边进行分块，为了就是解决
这个问题。
顶点3属于两个点双分量。所以不能存点了。
那么如果对边进行分块的话，判断到某个点是割点的时候，就把当前拥有的边弹出即可。直到判断cur结点是割点的那条边。
细节看看代码吧， 有分反向边和非反向边。注意一条边可能会被枚举两次（无向图加边两次），然后就是else if那里可以判断出来是否枚举过了。
还有就是一个割点会被多次枚举。
例如
有三条边
1 2
1 3
1 4
那么每条边都是一个不同的联通分量。
点的联通分量等于割点 + 1？我感觉不是，上面那个例子就不是了。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int maxn = 100000 + 20; struct Edge { int u, v, id; int tonext; }e[maxn * 2]; int first[maxn], num; void addEdge(int u, int v, int id) { ++num; e[num].u = u, e[num].v = v, e[num].id = id; e[num].tonext = first[u]; first[u] = num; } int DFN[maxn], low[maxn], when; int st[maxn], top; int id[maxn], toSelid; int ans[maxn]; bool flag[maxn]; const int root = 1; void tarjan(int cur, int fa) { DFN[cur] = low[cur] = ++when; for (int i = first[cur]; i; i = e[i].tonext) { int v = e[i].v; if (v == fa) continue; if (!DFN[v]) { st[++top] = e[i].id; tarjan(v, cur); low[cur] = min(low[cur], low[v]); if (low[v] >= DFN[cur]) { //这个是割点，特殊情况是两点一边，同一个割点会多次判定 ++toSelid; do { int eID = st[top--]; id[eID] = toSelid; // 这条边属于那一个块 ans[toSelid] = min(ans[toSelid], eID); } while (st[top + 1] != e[i].id); } } else if (DFN[cur] > DFN[v]) { //5-->4反向边，但是4同样会枚举4-->5这条边，这是没用的边，已经统计了 low[cur] = min(low[cur], DFN[v]); st[++top] = e[i].id; //反向边 } } } void solveTarjan(int n) { memset(DFN, 0, sizeof DFN); memset(low, 0, sizeof low); when = top = toSelid = 0; for (int i = 1; i <= n; ++i) { if (!DFN[i]) tarjan(i, i); } } void work() { int n, m; cin >> n >> m; for (int i = 1; i <= m; ++i) { int u, v; cin >> u >> v; addEdge(u, v, i); addEdge(v, u, i); } memset(ans, 0x3f, sizeof ans); solveTarjan(n); cout << toSelid << endl; for (int i = 1; i <= m; ++i) { cout << ans[id[i]] << " "; } } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif work(); return 0; }
hihocoder #1190 : 连通性·四 点双联通分量