14571

해결 방법

1) i in for all vertex

2-1) j in for all edges[i]

3) k in for all edges[j]

4) if(connect(j,k))

cycle++;

duplication[k]++;

2-2) ret += cycle/2*(cycle/2-1)/2

(1,2) (2,1) 중복되게 계산 되므로 2로 나누어 주어야한다.

2-3) j in for all vertex

ret -= duplication[j]*(duplication[j]-1)/2

하나의 겹치는 교점을 정해 놓고.1)

길이가 3인 사이클을 모두 찾는다.

그러면 모래시계의 조합은 사이클의 갯수가 n일때 nC2가 된다.

그런데 겹치는 것이 존재한다. 즉 교점이 1개가 아니라 2개가 되는 경우가 발생한다.!!!

그래서 겹치는 것의 모래시계의 경우의수를 빼줌으로써 전체 갯수를 구할 수 있게 된다.

 

아래는 소스코드이다.

#include <iostream> 

#include <iterator>

#include <algorithm> 

#include <vector>

#include <list>

#include <map>

#include <set>

#include <queue>

#include <stack>

#include <string>

#include <cmath>

#include <cstdio>

#include <cstring>

using namespace std;

#define MOD 1000000007

#define INF 2147483647

#define LNF 9223372036854775807

#define pb push_back

#define mp make_pair

typedef long long ll;

typedef unsigned long long ull;

typedef pair<ll,ll> pll;

typedef pair<int,int> pii;

int n,m,edge[201][201],duplication[201];

vector<int> edges[201];

int main(){

freopen("sample.txt","r",stdin);

scanf("%d%d",&n,&m);

for(int i=0,a,b;i<m;i++){

scanf("%d%d",&a,&b);

edges[a].pb(b);

edges[b].pb(a);

edge[a][b]=edge[b][a]=1;

}

ll ret=0;

for(int i=1,cycleCnt;i<=n;i++){

cycleCnt=0;

memset(duplication,0,sizeof(duplication));

for(int j=0,u;j<edges[i].size();j++){

u=edges[i][j];

for(int k=0,v;k<edges[u].size();k++){

v=edges[u][k];

if(edge[i][v]==1){

cycleCnt++;

duplication[v]++;

}

}

}

cycleCnt/=2;

ret += cycleCnt*(cycleCnt-1)/2;

for(int j=1;j<=n;j++) ret -= duplication[j]*(duplication[j]-1)/2;

}

printf("%lld\n",ret);

return 0;

}