http://hihocoder.com/problemset/problem/1190?sid=1051696
先抄襲一下
時間限制:10000ms
單點時限:1000ms
記憶體限制:256MB
描述
小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;
}