问题 J: Boomerangs

时间限制: 1 Sec 内存限制: 128 MB

提交 状态 题面

题目描述

Let G = (V,E) be a simple undirected graph with N vertices and M edges, where V = {1, …,N}. A tuple <u,v,w> is called as boomerang in G if and only if and u ≠ w, in other words, a boomerang consists of two edges which share a common vertex.

Given G, your task is to find as many disjoint boomerangs as possible in G. A set S contains disjoint boomerangs if and only if each edge in G only appears at most once (in one boomerang) in S. You may output any valid disjoint boomerangs, but the number of disjoint boomerangs should be maximum.

For example, consider a graph G = (V,E) of N = 5 vertices and M = 7 edges where E = [(1, 2), (1, 4),(2, 3), (2, 4), (2, 5), (3, 4), (3, 5)].

The maximum number of disjoint boomerangs in this example graph is 3. One example set containing the 3 disjoint boomerangs is [<4, 1, 2>, <4, 3, 2>, <2, 5, 3>], no set can contain more than 3 disjoint boomerangs in this example.

输入

Input begins with a line containing two integers: N M (1≤N,M≤100000), representing the number of vertices and the number edges in G, respectively. The next M lines, each contains two integers: ui vi(1≤ui < vi≤N), representing the edge (ui, vi) in G. You may safely assume that each edge appears at most once in the given list.

输出

Output contains an integer: K, representing the maximum number of disjoint boomerangs in G.

样例输入

5 7

1 2

1 4

2 3

2 4

2 5

3 4

3 5

样例输出

3

队友过的，不要想太复杂就可以了

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>

using namespace std;
typedef  long long ll;
const int N  = 200010;
typedef pair<int,int>P;
struct node
{
    int to,nex;
}grp[N];

int deg[N],head[N],cnt;
int n,m;
bool vis[N];
void add(int u,int v)
{
    grp[++cnt].to=v;
    grp[cnt].nex=head[u];
    head[u]=cnt;
    grp[++cnt].to=u;
    grp[cnt].nex=head[v];
    head[v]=cnt;
}

int dfs(int x,int nx)
{
    //cout<<x<<endl;
    if(vis[x]) return 0;
    vis[x]=true;
    int sum=0;
    for(int i=head[x];i;i=grp[i].nex)
    {
        int v=grp[i].to;
        sum++;
        sum+=dfs(v,x);
    }
    return sum;
}
int main()
{
    int ans=0;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            int sum=dfs(i,-1);
            //cout<<sum<<endl;
            ans+=(sum>>2);
        }
    }
    printf("%d\n",ans);
    return 0;
}