【题目描述】
有一个公园有n个景点,公园的管理员准备修建m条道路,并且安排一些形成回路的参观路线。如果一条道路被多条道路公用,那么这条路是冲突的;如果一条道路没在任何一个回路内,那么这条路是不冲突的
问分别有多少条有冲突的路和没有冲突的路
【题解】
这是一道点双联通的题,首先把图缩成块,显然如果块中边的数量大于点的数量,那么块中所有的边都是冲突的。
对于没有冲突的边,其实就是桥,tarjan的时候顺便求一下就行了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<algorithm>
using namespace std;
#define MAXN 10010
struct node{int y,next;}e[];
int n,m,ans1,ans2,len,top,dfs_clock,bcnt,belong[MAXN],Link[MAXN],dfn[MAXN],low[MAXN],stack[MAXN],vis[MAXN];
inline int read()
{
int x=,f=; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-; ch=getchar();}
while(isdigit(ch)) {x=x*+ch-''; ch=getchar();}
return x*f;
}
void insert(int x,int y) {e[++len].next=Link[x];Link[x]=len;e[len].y=y;}
void pre()
{
ans1=ans2=len=top=dfs_clock=;
memset(Link,,sizeof(Link));
memset(dfn,,sizeof(dfn));
}
void count()
{
int sum=;
for(int i=;i<=bcnt;i++)
{
int x=belong[i];
for(int j=Link[x];j;j=e[j].next)
if(vis[e[j].y]) sum++;
}
sum/=;
if(sum>bcnt) ans2+=sum;
}
void tarjan(int x,int father)
{
dfn[x]=low[x]=++dfs_clock;
stack[++top]=x;
for(int i=Link[x];i;i=e[i].next)
{
if(e[i].y==father) continue;
if(!dfn[e[i].y])
{
tarjan(e[i].y,x);
low[x]=min(low[x],low[e[i].y]);
if(low[e[i].y]>dfn[x]) ans1++;
if(low[e[i].y]>=dfn[x])
{
int y; bcnt=;
memset(vis,,sizeof(vis));
do
{
y=stack[top--];
vis[y]=;
belong[++bcnt]=y;
}while(e[i].y!=y);
belong[++bcnt]=x;
vis[x]=;
count();
}
}
else low[x]=min(low[x],dfn[e[i].y]);
}
}
void solve()
{
for(int i=;i<n;i++) if(!dfn[i]) tarjan(i,-);
printf("%d %d\n",ans1,ans2);
}
int main()
{
//freopen("cin.in","r",stdin);
//freopen("cout.out","w",stdout);
while(scanf("%d%d",&n,&m)==)
{
if(n==&&m==) break;
pre();
for(int i=;i<=m;i++) {int x=read(),y=read(); insert(x,y); insert(y,x);}
solve();
}
return ;
}