[POJ3177]Redundant Paths（双连通图，割边，桥，重边）

题目链接：http://poj.org/problem?id=3177

和上一题一样，只是有重边。

如何解决重边的问题？

1、  构造图G时把重边也考虑进来，然后在划分边双连通分量时先把桥删去，再划分，其中桥的一端的割点归入当前正在划分的边双连通分量。这个处理比较麻烦；

2、  在输入图G的边时，若出现重边，则不把重边放入图G，然后在划分边双连通分量时依然用Low划分。

 /*

 ━━━━━┒ギリギリ♂ eye！

 ┓┏┓┏┓┃キリキリ♂ mind！

 ┛┗┛┗┛┃＼○／

 ┓┏┓┏┓┃ /

 ┛┗┛┗┛┃ノ)

 ┓┏┓┏┓┃

 ┛┗┛┗┛┃

 ┓┏┓┏┓┃

 ┛┗┛┗┛┃

 ┓┏┓┏┓┃

 ┛┗┛┗┛┃

 ┓┏┓┏┓┃

 ┃┃┃┃┃┃

 ┻┻┻┻┻┻

 */

 #include <algorithm>

 #include <iostream>

 #include <iomanip>

 #include <cstring>

 #include <climits>

 #include <complex>

 #include <fstream>

 #include <cassert>

 #include <cstdio>

 #include <bitset>

 #include <vector>

 #include <deque>

 #include <queue>

 #include <stack>

 #include <ctime>

 #include <set>

 #include <map>

 #include <cmath>

 using namespace std;

 #define fr first

 #define sc second

 #define cl clear

 #define BUG puts("here!!!")

 #define W(a) while(a--)

 #define pb(a) push_back(a)

 #define Rint(a) scanf("%d", &a)

 #define Rll(a) scanf("%lld", &a)

 #define Rs(a) scanf("%s", a)

 #define Cin(a) cin >> a

 #define FRead() freopen("in", "r", stdin)

 #define FWrite() freopen("out", "w", stdout)

 #define Rep(i, len) for(int i = 0; i < (len); i++)

 #define For(i, a, len) for(int i = (a); i < (len); i++)

 #define Cls(a) memset((a), 0, sizeof(a))

 #define Clr(a, x) memset((a), (x), sizeof(a))

 #define Full(a) memset((a), 0x7f7f, sizeof(a))

 #define lp p << 1

 #define rp p << 1 | 1

 #define pi 3.14159265359

 #define RT return

 typedef long long LL;

 typedef long double LD;

 typedef unsigned long long ULL;

 typedef pair<int, int> pii;

 typedef pair<string, int> psi;

 typedef map<string, int> msi;

 typedef vector<int> vi;

 typedef vector<LL> vl;

 typedef vector<vl> vvl;

 typedef vector<bool> vb;

 typedef struct Edge {

     int v;

     bool cut;

     Edge() {}

     Edge(int vv) : v(vv) { cut = ; }

 }Edge;

 const int maxn = ;

 const int maxm = ;

 int n, m;

 int dig[maxn];

 int dfn[maxn], low[maxn], idx;

 vector<Edge> G[maxn];

 bool vis[maxn];

 int st[maxn], top;

 int belong[maxn], bcnt;

 void tarjan(int u, int p) {

     int v;

     low[u] = dfn[u] = ++idx;

     vis[u] = ;

     st[top++] = u;

     Rep(i, G[u].size()) {

         v = G[u][i].v;

         if(v == p) continue;

         if(!dfn[v]) {

             tarjan(v, u);

             low[u] = min(low[u], low[v]);

             if(low[v] > dfn[u]) {

                 G[u][i].cut = ;

                 Rep(j, G[v].size()) {

                     if(G[v][j].v== u) {

                         G[v][j].cut = ;

                         break;

                     }

                 }

             }

         }

         else if(vis[v]) low[u] = min(low[u], dfn[v]);

     }

     if(low[u] == dfn[u]) {

         bcnt++;

         do {

             v = st[--top];

             vis[v] = ;

             belong[v] = bcnt;

         } while(v != u);

     }

 }

 int main() {

     FRead();

     int u, v;

     while(~Rint(n) && ~Rint(m)) {

         Rep(i, n+) G[i].cl();

         Cls(vis); Cls(dig); Cls(dfn); Cls(low);

         top = ; idx = ; bcnt = ;

         Rep(i, m) {

             Rint(u); Rint(v);

             G[u].pb(Edge(v)); G[v].pb(Edge(u));

         }

         tarjan(, );

         int ret = ;

         For(u, , n+) {

             printf("%d ", belong[u]);

             Rep(i, G[u].size()) {

                 if(G[u][i].cut) {

                     dig[belong[u]]++;

                 }

             }

         }

         printf("\n");

         For(i, , bcnt+) {

             if(dig[i] == ) ret++;

         }

         printf("%d\n", (ret+)>>);

     }

     RT ;

 }