Hdu 6184三元リングカウント

918 ワード

タイトルは1つの2 e 5点2 e 5辺の無方向図に説明して,サブ図{V=(A,B,C,D)E=(AB,BC,CD,DA,AC)}の数量を求めます.HINTは,すべてのエッジを指向し,度数の小さい点から度数の大きい点連に向かうことを考慮し,各点の出度がsqrt(2 e 5)より小さいようにした.
   #include 
    using namespace std;
    typedef long long ll;
    const int maxn=200007;
    int n,m;
    int x[maxn],y[maxn],d[maxn];
    vector >g[maxn];
    int cnt[maxn],vis[maxn],id[maxn];
    int main(){
    	while(~scanf("%d%d",&n,&m)){
    		for(int i=1;i<=n;i++)d[i]=0;
    		for(int i=1;i<=n;i++)g[i].clear();
    		for(int i=1;i<=m;i++)cnt[i]=vis[i]=0;
    		for(int i=1;i<=m;i++){
    			scanf("%d%d",&x[i],&y[i]);
    			d[x[i]]++;
    			d[y[i]]++;
    		}
    		for(int i=1;i<=m;i++){
    			if(d[x[i]]