Submission #1193409

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193409		vnedu	우호 조약 체결 (JOI14_friends)	C++17	0 / 100	25 ms	4932 KiB

friends

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }

#define fi first
#define se second

#define pb push_back
#define ii pair<int, int>

#define all(x) x.begin(), x.end()

#define TASK "nonsense"

/// end of template ///

const int N = 1e5 + 10;
int n,m,par[N],vis[N],sz[N];
vector<int> adj[N];
int get(int x)
{
    if(x==par[x]) return x;
    return par[x]=get(par[x]);
}
void unite(int x, int y)
{
    int s=get(x),t=get(y);
    if(s==t) return;
    par[s]=t;
    sz[t]+=sz[s];
}
queue<int> q;
void solve()
{
    cin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int x,y; cin>>x>>y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    for(int i=1;i<=n;++i) par[i]=i,sz[i]=1;
    for(int i=1;i<=n;++i) if((int)adj[i].size()>1)
    {
        int root=adj[i][0];
        for(int x : adj[i])
        {
            unite(root,x);
            if(!vis[x])
            {
                q.push(x);
                vis[x]=x;
            }
            else
            {
                unite(vis[x],x);
            }
        }
    }
    while(!q.empty())
    {
        int u=q.front(); q.pop();
        for(int v : adj[u])
        {
            if(vis[v]) unite(vis[v],vis[u]);
            else
            {
                vis[v]=vis[u];
                q.push(v);
            }
        }
    }
    ll ans=0;
    for(int i=1;i<=n;++i) if(get(i)==i)
    {
        if(sz[i]==1) ans+=(int)adj[i].size();
        else ans+=sz[i]*1LL*(sz[i]-1)/2;
    }
    cout<<ans;
}
int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

//    freopen(TASK".inp","r",stdin);
//    freopen(TASK".out","w",stdout);

    int testcase=1;
//    cin>>testcase;

    while (testcase--)
        solve();

    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 65