Skip to content
Using Free University Tbilisi Mail with screen readers

1 of 5,550
(no subject)
Inbox
x

Zuka Kenchuashvili
Attachments
5:07 PM (0 minutes ago)
to me


Attachments area


Compose:
New Message
MinimizePop-outClose
To
elsamziuri@gmail.com
elsamziuri@gmail.com
elzamziuri@gmail.com
Subject


--
დავით ბეჟანიშვილი
მათემატიკისა და კომპიუტერული მეცნიერების სკოლის სტუდენტი
#include <bits/stdc++.h>
using namespace std;
int n,m,a[100001],b[100001],i,e,z,t,x,y,w,c;
bool fix[100001];
map <int , int> ma[100001];
void dfs(int v){
    int k;
    k=1;
    fix[v]=1;
    for(int j=1;j<=t;j++){
        if(ma[v][b[k]]==0 && v!=b[k]){
            swap(b[k],b[t]);
            t=t-1;
            dfs(b[t+1]);
        }
        else
        k++;
        if(k==t+1){
            break ;
        }
    }
}


int main(){
    cin>>n>>m;
    for(i=1;i<=m;i++){
        cin>>x>>y;
        ma[x][y]=1;
        ma[y][x]=1;
        a[x]=a[x]+1;
        a[y]=a[y]+1;
    }
    b[1]=1;
    t=n;
    for(i=2;i<=n;i++){
        b[i]=b[i-1]+1;
    }
    for(i=1;i<=n;i++){
        if(fix[i]==0 && a[i]<n-1){
            dfs(i);
            c++;
        }
    }

    for(i=1;i<=n;i++){
        if(a[i]<n-1){
            z++;
        }
    }
    e=n*(n-1)/2-m;
    w=n*(n-1)/2-n+1;
    if(e==z-c){
        if(w>=m){
            cout<<0<<endl;
        }
        else
        cout<<m-w<<endl;
        return 0;
    }
    if(w<=e-z+c){
        cout<<m<<endl;
        return 0;
    }
    w=w-e+z-c;
    if(w>=m){
        cout<<0<<endl;
    }
    else
    cout<<m-w<<endl;
    return 0;

}
0-1.cpp
Displaying 0-1.cpp.