Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <set>
- using namespace std;
- long long n,m;
- vector <vector <int> > G;
- vector <pair<int,int> > M;
- int dsu_parent[5000];
- int dsu_rank[5000];
- int size_of_component[5000];
- int edges_of_component[5000];
- set <int> all_components;
- long long C[5001][5001];
- long long answer_one=0,answer_two=0,answer_three=0,answer_four=0;
- long long real_answer=0;
- int MAXN=5000;
- ostream & operator<<(ostream &stream, vector <int> &A){
- for (int i=0;i<A.size();i++)
- cout<<A[i]<<" ";
- return stream;
- }
- int dsu_make(int i){
- dsu_parent[i]=i;
- dsu_rank[i]=0;
- }
- void pascal_init(){
- for (int i=0;i<=n;i++)
- C[i][i]=1,C[i][1]=i;
- for (int i=2;i<=n;i++)
- for (int j=2;j<=n-1;j++){
- C[i][j]=C[i-1][j-1]+C[i-1][j];
- //cout<<C[i][j]<<" "<<endl;
- }
- real_answer=C[n][1]+C[n][2]+C[n][3]+C[n][4];
- }
- int dsu_find(int i){
- if (i==dsu_parent[i])
- return i;
- return dsu_parent[i]=dsu_find(dsu_parent[i]);
- }
- void dsu_unite(int a, int b){
- a=dsu_find(a);
- b=dsu_find(b);
- if (a!=b){
- if (dsu_rank[a]<dsu_rank[b])
- swap(a,b);
- dsu_parent[b]=a;
- size_of_component[a]+=size_of_component[b];
- edges_of_component[a]+=edges_of_component[b];
- all_components.erase(b);
- if (dsu_rank[a]==dsu_rank[b])
- dsu_rank[a]++;
- }
- }
- void iterat_for_three(int numb){
- //cout<<"ENTEROFTHREE"<<endl;
- int u=M[numb].first; int v=M[numb].second;
- long long k1=G[u].size();
- long long k2=G[v].size();
- sort (G[u].begin(),G[u].end());
- sort (G[v].begin(),G[v].end());
- vector<int> intersect_of_lists(G[u].size()+G[v].size());
- vector<int>::iterator ite=set_intersection(G[u].begin(),G[u].end(),G[v].begin(),G[v].end(),intersect_of_lists.begin());
- long long e=ite-intersect_of_lists.begin();
- long long answer=(n-2)-k1-k2+e;
- answer_three+=answer;
- //cout<<"EXITOFTHREE"<<endl;
- }
- void iterat_for_four(int numb){
- long long answer=0;
- int u=M[numb].first;
- int v=M[numb].second;
- int u_comp=dsu_find(u); int v_comp=dsu_find(v);
- int part_sums[5001]={};
- int local_size[5001]={};
- int k=0;
- for (set<int>::iterator it=all_components.begin();it!=all_components.end();it++,k++){
- if (k) part_sums[k]+=part_sums[k-1];
- int cur=*it;
- if (cur!=u_comp && cur!=v_comp){
- part_sums[k]+=size_of_component[k];
- local_size[k]=size_of_component[k];
- answer+=(size_of_component[k]*(size_of_component[k]-1))/2-edges_of_component[k];
- }
- }
- for (int i=0;i<k;i++){
- long long cur_part_sum=0;
- cur_part_sum=part_sums[k-1];
- if (i) cur_part_sum-=part_sums[i-1];
- answer+=local_size[k]*cur_part_sum;
- }
- answer_four+=answer;
- dsu_unite(u,v);
- u_comp=dsu_find(u);
- G[u].push_back(v);
- G[v].push_back(u);
- edges_of_component[u_comp]++;
- //cout<<"EXIT"<<endl;
- }
- int main(){
- cin>>n>>m;
- G.resize(n);
- M.resize(m);
- answer_one=0; answer_two=m;
- for (int i=0;i<m;i++){
- int a,b; cin>>a>>b;
- a--; b--;
- if (a>b) swap(a,b);
- M[i]=(make_pair(a,b));
- }
- for (int i=0;i<n;i++){
- dsu_make(i);
- size_of_component[i]=1;
- all_components.insert(i);
- }
- for (int i=0;i<m;i++){
- iterat_for_three(i);
- iterat_for_four(i);
- }
- pascal_init();
- cout<<C[n][4]-answer_four<<" "<<C[n][3]-answer_three<<" "<<real_answer<<endl;
- cout<<real_answer-answer_one-answer_two-answer_three-answer_four<<endl;
- return 0;
- }
Add Comment
Please, Sign In to add comment