poj 3352 Road Construction

时间:2023-03-09 19:19:38
poj 3352 Road Construction
// 只能说这题和上题一模一样
// 我就直接贴上题代码了、、 #include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <string.h>
using namespace std;
#define MOD 1000000007
#define maxn 20100
#define maxm 5010
struct Edge{
int to;
int num;
int next;
Edge(){};
Edge(int u,int v){to=u;next=v;}
}E[maxn];
int V[maxm],num;
int pre[maxm];
int dfst,bcc;
int belong[maxm];
bool tag[maxn];
void init(int n){
dfst=;
num=;
bcc=;
for(int i=;i<=n;i++){
V[i]=-;
pre[i]=;
belong[i]=;
}
}
void add(int u,int v,int m){
E[num].to=v;
E[num].num=m;
E[num].next=V[u];
V[u]=num++; E[num].to=u;
E[num].num=m;
E[num].next=V[v];
V[v]=num++;
}
int dfs(int u,int fa){
int lowu;
lowu=pre[u]=++dfst;
int v,e;
for(e=V[u];e!=-;e=E[e].next){
v=E[e].to;
if(!pre[v]){
int lowv=dfs(v,u);
lowu=min(lowu,lowv);
if(lowv>pre[u]){
tag[E[e].num]=;
}
}
else if(v!=fa) lowu=min(lowu,pre[v]);
}
return lowu;
}
void dfsbcc(int u){
belong[u]=bcc;
int v,e;
for(e=V[u];e!=-;e=E[e].next){
if(tag[E[e].num]) continue;
v=E[e].to;
if(!belong[v]){
dfsbcc(v);
}
}
}
int rc[maxn][],in[maxm];
int main()
{
int F,R;
int u,v;
int i,j;
while(scanf("%d %d",&F,&R)!=EOF){
init(F);
for(i=;i<=R;i++){
scanf("%d %d",&u,&v);
rc[i][]=u;rc[i][]=v;
add(u,v,i);
tag[i]=;
}
dfs(,);
for(i=;i<=F;i++)
if(!belong[i]){
bcc++;
dfsbcc(i);
}
for(i=;i<=bcc;i++) in[i]=;
for(i=;i<=R;i++)
{
u=belong[rc[i][]];
v=belong[rc[i][]];
if(u!=v){
in[u]++;
in[v]++;
}
}
int ans=;
for(i=;i<=bcc;i++) if(in[i]==) ans++; printf("%d\n",(ans+)/); }
return ;
}