CF659E New Reform

原题传送门

分析：即求环的数量，但由于是无向图，所以中间还要将两个点之间的环去掉

代码：

#include <bits/stdc++.h>

using namespace std;

const int N=200005;
int n,m;

struct Node
{
    int nxt,to,w;
}e[N];

int tot,head[N];
void add(int u,int v)
{
    e[++tot].nxt=head[u];
    e[tot].to=v;
    head[u]=tot;
}

int vis[N],fg;
void dfs(int u,int st)
{
    for(int i=head[u]; i ;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v==st) continue ;//即两个点成的环
        if(!vis[v])
        {
            vis[v]=1;
            dfs(v,u);
        }
        else fg=1;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }

    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            fg=0;
            vis[i]=1;
            dfs(i,i);
            if(!fg) ans++;
        }
    }

    cout<<ans<<endl;

    return 0;
}