poj3352 Road Construction & poj3177 Redundant Paths （边双连通分量）题解

题意：有n个点，m条路，问你最少加几条边，让整个图变成边双连通分量。

思路：缩点后变成一颗树，最少加边 = （度为1的点 + 1）/ 2。3177有重边，如果出现重边，用并查集合并两个端点所在的缩点后的点。

代码：

/**/

#include<set>

#include<map>

#include<stack>

#include<cmath>

#include<queue>

#include<vector>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

typedef long long ll;

const int maxn =  + ;

const int seed = ;

const ll MOD = 1e9 + ;

const int INF = 0x3f3f3f3f;

using namespace std;

struct Edge{

    int u, v, next;

}edge[maxn << ];

int index, scc_cnt, tot;    //scc_cnt记录SCC

int dfn[maxn], low[maxn], sccno[maxn], in[maxn], head[maxn];

stack<int> s;

void addEdge(int u, int v){

    edge[tot].v = v;

    edge[tot].u = u;

    edge[tot].next = head[u];

    head[u] = tot++;

}

void tarjan(int u, int pre){

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

    s.push(u);

    for(int i = head[u]; i != -; i = edge[i].next){

        int v = edge[i].v;

        if(!dfn[v]){

            tarjan(v, u);

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

        }

        else if(v != pre){

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

        }

    }

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

        scc_cnt++;

        int a;

        while(){

            a=s.top();

            s.pop();

            sccno[a] = scc_cnt;

            if(a == u) break;

        }

    }

}

int main(){

    int n, m;

    scanf("%d%d", &n, &m);

    index = scc_cnt = tot = ;

    while(!s.empty()) s.pop();

    memset(head, -, sizeof(head));

    memset(dfn, , sizeof(dfn));

    memset(sccno, , sizeof(sccno));

    for(int i = ; i < m; i++){

        int u, v;

        scanf("%d%d", &u, &v);

        addEdge(u, v);

        addEdge(v, u);

    }

    for(int i = ; i <= n; i++){

        if(!dfn[i])

            tarjan(i, );

    }

    memset(in, , sizeof(in));

    for(int i = ; i < tot; i += ){

        int u = edge[i].u, v = edge[i].v;

        if(sccno[u] != sccno[v]){

            in[sccno[u]]++;

            in[sccno[v]]++;

        }

    }

    int cnt = ;

    for(int i = ; i <= scc_cnt; i++){

        if(in[i] == ) cnt++;

    }

    printf("%d\n", (cnt + ) / );

    return ;

}

/**/

#include<set>

#include<map>

#include<stack>

#include<cmath>

#include<queue>

#include<vector>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

typedef long long ll;

const int maxn =  + ;

const int seed = ;

const ll MOD = 1e9 + ;

const int INF = 0x3f3f3f3f;

using namespace std;

struct Edge{

    int u, v, next;

}edge[maxn << ];

int index, scc_cnt, tot;    //scc_cnt记录SCC

int dfn[maxn], low[maxn], sccno[maxn], in[maxn], head[maxn];

stack<int> s;

map<int, int> mp[maxn];

int Find(int x){

    return sccno[x] == x? x : sccno[x] = Find(sccno[x]);

}

void addEdge(int u, int v){

    edge[tot].v = v;

    edge[tot].u = u;

    edge[tot].next = head[u];

    head[u] = tot++;

}

void tarjan(int u, int pre){

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

    s.push(u);

    for(int i = head[u]; i != -; i = edge[i].next){

        int v = edge[i].v;

        if(!dfn[v]){

            tarjan(v, u);

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

        }

        else if(v != pre){

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

        }

    }

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

        scc_cnt++;

        int a;

        while(){

            a=s.top();

            s.pop();

            sccno[a] = u;

            if(a == u) break;

        }

    }

}

int main(){

    int n, m;

    scanf("%d%d", &n, &m);

    index = scc_cnt = tot = ;

    while(!s.empty()) s.pop();

    memset(head, -, sizeof(head));

    memset(dfn, , sizeof(dfn));

    memset(sccno, , sizeof(sccno));

    for(int i = ; i < m; i++){

        int u, v;

        scanf("%d%d", &u, &v);

        addEdge(u, v);

        addEdge(v, u);

    }

    for(int i = ; i <= n; i++){

        if(!dfn[i])

            tarjan(i, );

    }

    for(int i = ; i <= n; i++) mp[i].clear();

    memset(in, , sizeof(in));

    for(int i = ; i < tot; i += ){

        int u = edge[i].u, v = edge[i].v;

        if(u > v) swap(u, v);

        mp[u][v]++;

        if(mp[u][v] == ){

            int fx = Find(u), fy = Find(v);

            if(fx != fy){

                sccno[fx] = fy;

            }

        }

    }

    for(int i = ; i < tot; i += ){

        int u = edge[i].u, v = edge[i].v;

        int fx = Find(u), fy = Find(v);

        if(fx != fy){

            in[fx]++;

            in[fy]++;

        }

    }

    int cnt = ;

    for(int i = ; i <= n; i++){

        if(sccno[i] == i && in[i] == ) cnt++;

    }

    printf("%d\n", (cnt + ) / );

    return ;

}