JOI2014春day2-friends
何 故 通 っ た
証明もなしに適当に書いて通った問題初めてな気がする
通った瞬間小躍りしました
出次数2以上のやつからたどり着ける奴らは完全グラフになることに気づく
出次数2以上の点A,Bがあり、A->C,B->C(間接的でも良い)の時Aによる完全グラフとBによる完全グラフが合体する
→unionfind
ループとかの挙動どうなってるか全くわからんかったけど投げたら通りました(適当)
#include <iostream> #include <cstdio> #include <vector> using namespace std; #define rep(i,n) for(int i=0;i<(n);++i) #define rep1(i,n) for(int i=1;i<=(n);++i) #define ALL(c) (c).begin(),(c).end() typedef long long ll; vector<int> G[100000],Ginv[100000],Gboth[100000]; bool visited[100000],kyo[100000]; int par[100000],cnt[100000]; struct UnionFind{ void init(int n){ rep(i,n) par[i]=i; } int find(int x){ if(x==par[x]) return x; return par[x]=find(par[x]); } void unite(int x,int y){ x=find(x); y=find(y); if(x==y) return; par[x]=y; } bool same(int x,int y){ return find(x)==find(y); } }; UnionFind uf; void dfs(int id){ if(visited[id]) return; if(!kyo[id]) return; visited[id]=true; rep(j,G[id].size()){ kyo[G[id][j]]=true; dfs(G[id][j]); } } int main(){ int n,m; cin >> n >> m; rep(i,m){ int a,b; scanf("%d%d",&a,&b); a--;b--; G[a].push_back(b); Ginv[b].push_back(a); Gboth[a].push_back(b); Gboth[b].push_back(a); } uf.init(n); rep(i,n){ if(G[i].size()>1){ rep(j,G[i].size()) kyo[G[i][j]]=true; rep(j,G[i].size()-1) uf.unite(G[i][j],G[i][j+1]); } } rep(i,n) dfs(i); rep(i,n) visited[i]=false; rep(i,n){ if(!kyo[i]) continue; // cout << i; rep(j,Gboth[i].size()){ if(kyo[Gboth[i][j]]) uf.unite(i,Gboth[i][j]); } } // cout << endl; ll ans=0; rep(i,n) cnt[uf.find(i)]++; rep(i,n){ // cout << cnt[i]; ans+=((ll)cnt[i]*(cnt[i]-1)); } // cout << endl; rep(i,n){ rep(j,G[i].size()){ if(!kyo[i]) ans++; } } cout << ans << endl; return 0; }