Any questions?
Reply Back New Topic
View Topic

求助!这个题我为什么不对啊


#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#define ll long long
#define rint register int
using namespace std;
template<typename xxx>void read(xxx &x)
{
    x=0;int f=1;char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
    for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    x*=f;
}
template<typename xxx>void print(xxx x)
{
    if(x<0){putchar('-');x=-x;}
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
const int maxn=100200;
int n,m;
struct edge{
    int to,last;
}e[maxn<<1];
int tot,head[maxn];
inline void add(int from,int to)
{
    tot++;
    e[tot].to=to;
    e[tot].last=head[from];
    head[from]=tot;    
}
int dfn[maxn],low[maxn],sum;
int vis[maxn],st[maxn],top;
int cut[maxn],rt,pre[maxn];
int tarjan(int u,int fa)
{
    dfn[u]=low[u]=++sum;
    pre[u]=fa;
    for(rint i=head[u];i;i=e[i].last)
    {
        int v=e[i].to;
        if(!dfn[v])
        {
            tarjan(v,u);
            if(low[u]>low[v]) low[u]=low[v];
        }
        else if(fa!=v&&low[u]>dfn[v]) low[u]=dfn[v];
    }
}
void count()
{
    int cnt=0,ans1=0,ans2=0;
    for(rint i=1;i<=n;i++) if(!dfn[i]) tarjan(i,0);
    for(rint i=2;i<=n;++i)
    {
        int v=pre[i];
        if(v==1) cnt++;
        else if(low[i]>=dfn[v]) cut[v]=1,ans1++;
    }
    if(cnt>1) cut[1]=1,ans1++;
    for(rint i=1;i<=n;++i)
    {
        int v=pre[i];
        if(v>0&&low[i]>dfn[v]) ans2++;
    }
    printf("%d %d\n",ans1,ans2);
    for(rint i=1;i<=n;++i) if(cut[i]) printf("%d\n",i);
}
int main()
{
    while(scanf("%d%d",&n,&m))
    {
        if(n==0&&m==0) break;
        tot=0;
        memset(cut,0,sizeof(cut));
        memset(low,0,sizeof(low));
        memset(dfn,0,sizeof(dfn));
        memset(pre,0,sizeof(pre));
        memset(head,0,sizeof(head));
        for(rint i=1;i<=m;i++)
        {
            int a,b;
            read(a);read(b);
            add(a,b);add(b,a);
        }
        count();
    }
    return 0;
}