（连通图 ） Redundant Paths --POJ --3177

链接：

http://poj.org/problem?id=3177

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=82833#problem/E

要去重边， 求再加上几条边任意两点直接都能到达

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

using namespace std;

#define N 100005

struct Edage

{

    int v, next;

} e[N<<];

int n, Index, bnt, cnt, top;

int low[N], dfn[N], Head[N], Stack[N], belong[N], ru[N];

bool use[][];

void Init()

{

    Index = bnt = top = ;

    memset(low, , sizeof(low));

    memset(dfn, , sizeof(dfn));

    memset(Head, -, sizeof(Head));

    memset(use, , sizeof(use));

    memset(belong, , sizeof(belong));

    memset(ru, , sizeof(ru));

}

void Add(int u, int v)

{

    e[bnt].v = v;

    e[bnt].next = Head[u];

    Head[u] = bnt++;

}

void Tarjan(int u, int fa)

{

    int v;

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

    Stack[++top] = u;

    for(int j=Head[u]; j!=-; j=e[j].next)

    {

        v = e[j].v;

        if(!dfn[v])

        {

            Tarjan(v, u);

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

        }

        else if(v!=fa)

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

    }

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

    {

        cnt++;

        do

        {

            v = Stack[top--];

            belong[v] = cnt;

        }while(u!=v);

    }

}

int main()

{

    int  m;

    while(scanf("%d%d", &n, &m)!=EOF)

    {

        int i, j, u, v;

        Init();

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

        {

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

            if(use[u][v]==false)

            {

                Add(u, v);

                Add(v, u);

                use[u][v] = use[v][u] = true;

            }

        }

        Tarjan(, );

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

            for(j=Head[i]; j!=-; j=e[j].next)

            {

                if(belong[i]!=belong[e[j].v])

                    ru[belong[i]]++;

            }

        int ans=;

        for(i=; i<=cnt; i++)

        {

            if(ru[i]==)

                ans++;

        }

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

    }

    return ;

}

又看了一遍连通图， 把之前的题都看了一遍，虽然现在该学匹配了，我却还在这下功夫，但这是有点作用的，下次再复习一下估计理解就更好了