1 solutions
-
0
C++ :
/* author :hzoi_ztx title :棋子 ALG :DFS CMT :二分图思想 嗯,只能说忘了KM怎么写了 = = 将未访问过的点加入集合,然后模拟模拟就粗来了 预计能过一些点吧 [2014 10 23] */ #include <cstdio> #include <map> #define maxn 200010 #define maxe 500010 #define maxt 400010 typedef long long ll ; struct FST{ ll to , next ; } e[maxe] ; ll star[maxt] = {0} , tote = 0 ; void addEdge(ll u , ll v) { tote ++ ; e[tote].to = v ; e[tote].next = star[u] ; star[u] = tote ; } ll n , ans = 0 ; ll cntx = 0 , cnty = 200000 ; std::map<ll,ll>existx ; std::map<ll,ll>existy ; bool visit[maxt] = {0} ; ll Left , Right ; void dfs(ll s, bool left) { ll t , p ; if (left) { Left ++ ; ans += Right ; } else { Right ++ ; ans += Left ; } for (p=star[s],t=e[p].to;p;p=e[p].next,t=e[p].to) { if (!visit[t]) { visit[t] = true ; dfs(t , !left) ; } } } int main() { // #define READ #ifdef READ freopen("chess.in" ,"r",stdin ) ; freopen("chess.out","w",stdout) ; #endif ll i , x , y ; scanf("%lld", &n ) ; existx.clear() ; existy.clear() ; for (i = 1 ; i <= n ; i ++ ) { scanf("%lld%lld", &x , &y ) ; if (existx[x]) x = existx[x] ; else { existx[x] = ++cntx ; x = cntx ; } if (existy[y]) y = existy[y] ; else { existy[y] = ++cnty ; y = cnty ; } addEdge(x , y) ; addEdge(y , x) ; } for (i = 1 ; i <= cntx ; i ++ ) { if (!visit[i]) { visit[i] = true ; Left = 0 ; Right = 0 ; dfs(i , true) ; } } printf("%lld\n", ans ) ; #ifdef READ fclose(stdin ) ; fclose(stdout) ; #endif return 0 ; }
- 1
Information
- ID
- 591
- Time
- 1000ms
- Memory
- 128MiB
- Difficulty
- (None)
- Tags
- # Submissions
- 0
- Accepted
- 0
- Uploaded By