这个题有点问题 输入有重边，要先去重，重边算一条边 求边双连通和强联通算法一样。 #includecstdio#includestring.h#includemath.h#includequeue#includestack#define N 5010#define M 10100using namespace std;stru
这个题有点问题
输入有重边，要先去重，重边算一条边
求边双连通和强联通算法一样。
#include<cstdio>
#include<string.h>
#include<math.h>
#include<queue>
#include<stack>
#define N 5010
#define M 10100
using namespace std;
struct edge{
int u,v,next;
}edge[M*2];
int n,m;
int cnt,head[N];
int scc,num,dfn[N],low[N],belong[N];
bool instack[N];
int d[N];
bool map[N][N];
stack<int>sta;
void addedge(int u,int v){
edge[cnt].u=u;
edge[cnt].v=v;
edge[cnt].next=head[u];
head[u]=cnt++;
edge[cnt].u=v;
edge[cnt].v=u;
edge[cnt].next=head[v];
head[v]=cnt++;
}
int MAX(int a,int b){
return a>b?a:b;
}
int MIN(int a,int b){
return a>b?b:a;
}
void tarjan(int u,int father){
dfn[u]=low[u]=++num;
sta.push(u);
instack[u]=true;
for(int j=head[u];j!=-1;j=edge[j].next){
int v=edge[j].v;
if(v==father)continue;
if(dfn[v]==0){
tarjan(v,u);
low[u]=MIN(low[v],low[u]);
}
else
low[u]=MIN(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
scc++;
while(1){
int tem=sta.top();
sta.pop();
belong[tem]=scc;
if(tem==u)break;
}
}
}
void init(){
scc=cnt=num=0;
memset(head,-1,sizeof(head));
memset(dfn,0,sizeof(dfn));
memset(d,0,sizeof(d));
memset(instack,0,sizeof(instack));
memset(map,0,sizeof(map));
}
int main(){
int i,j,u,v;
scanf("%d %d",&n,&m);
init();
for(i=1;i<=m;i++){
scanf("%d %d",&u,&v);
if(map[u][v])continue;
addedge(u,v);
map[u][v]=map[v][u]=1;
}
tarjan(1,0);
for(i=0;i<cnt;i++){
if(low[edge[i].v]!=low[edge[i].u])
d[belong[edge[i].v]]++,d[belong[edge[i].u]]++;
}
int ans=0;
for(i=1;i<=scc;i++)
if(d[i]==2)
ans++;
printf("%d\n",(ans+1)/2);
}