///1085422276 #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<queue> #include<cmath> #include<map> #include<bitset> #include<set> #include<vector> using namespace std ; typedef __int64 ll; #define mem(a) memset(a,0,sizeof(a)) #define meminf(a) memset(a,127,sizeof(a)); #define memfy(a) memset(a,-1,sizeof(a)); #define TS printf("111111\n"); #define FOR(i,a,b) for( int i=a;i<=b;i++) #define FORJ(i,a,b) for(int i=a;i>=b;i--) #define READ(a,b,c) scanf("%d%d%d",&a,&b,&c) #define mod 1000000007 #define inf 100000000 inline ll read() { ll x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘)f=-1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) { x=x*10+ch-‘0‘; ch=getchar(); } return x*f; } //**************************************** #define maxn 1000000+6 struct ss { int to,next; } e[maxn]; struct node { int x,index;//0,1; }; int head[maxn],n,a,b,t,in[maxn][2],A,B,C; map<pair<int ,int >,int >mp; map<int ,int >vis,vis2; map<int ,vector<int > >mpp,mpp2; vector<int >V1,V2; vector<int >::iterator it;; int main() { int T=read(); int oo=1; while(T--) { // init(); scanf("%d",&n); mp.clear(); V1.clear(); V2.clear(); mpp2.clear(); mpp.clear(); vis.clear(); vis2.clear(); int k=0; FOR(i,1,n) { scanf("%d%d",&a,&b); if(mp[make_pair(a,b)])continue; mpp[a].push_back(b); mpp2[b].push_back(a); if(!vis[a]) V1.push_back(a); if(!vis2[b]) V2.push_back(b); vis[a]=1; vis2[b]=1; mp[make_pair(a,b)]=1; } A=0; B=0; C=0; int sum; for(int i=0; i<V1.size(); i++) { sum=0; for(it=mpp[V1[i]].begin(); it!=mpp[V1[i]].end(); it++) { sum+=mpp2[*it].size(); } if(sum==mpp[V1[i]].size()) { if(sum==1) C++; else { A++; } } } for(int i=0; i<V2.size(); i++) { sum=0; for(it=mpp2[V2[i]].begin(); it!=mpp2[V2[i]].end(); it++) { sum+=mpp[*it].size(); } if(sum==mpp2[V2[i]].size()) { //cout<<mpp[V2[i]].size()<<endl; if(sum==1) C++; else { B++; } } } printf("Case #%d: ",oo++); cout<<A<<" "<<B<<" "<<C/2<<endl; } return 0; }
HDU 5489 Difference of Clustering 图论
原文:http://www.cnblogs.com/zxhl/p/4908819.html