1 solutions

  • 0
    @ 2024-12-10 23:10:28

    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