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

2023-09-05 阅读 26 评论 0

摘要：链接： http://poj.org/problem?id=3177 http://acm.hust.edu.cn/vjudge/contest/view.action?cid=82833#problem/E 要去重边，求再加上几条边任意两点直接都能到达代码： #include <iostream> #include <cstdio> #include <cst

链接：

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 100005struct Edage
{int v, next;
} e[N<<2];int n, Index, bnt, cnt, top;
int low[N], dfn[N], Head[N], Stack[N], belong[N], ru[N];
bool use[5005][5005];void Init()
{Index = bnt = top = 0;memset(low, 0, sizeof(low));memset(dfn, 0, sizeof(dfn));memset(Head, -1, sizeof(Head));memset(use, 0, sizeof(use));memset(belong, 0, sizeof(belong));memset(ru, 0, 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!=-1; 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=0; 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(1, 1);for(i=1; i<=n; i++)for(j=Head[i]; j!=-1; j=e[j].next){if(belong[i]!=belong[e[j].v])ru[belong[i]]++;}int ans=0;for(i=1; i<=cnt; i++){if(ru[i]==1)ans++;}printf("%d\n", (ans+1)>>1);}return 0;
}