#include <bits/stdc++.h>
#define DIMN 100005
#define DIMM 200005
using namespace std;
int low[DIMN] , bicnx , lvl[DIMN] , taken[DIMN] , f[DIMN] , two[DIMN] , under[DIMN];
stack <int> st;
vector <int> v[DIMN] , w[2 * DIMN];
set <int> sol[DIMN];
int x , n , val;
void dfs_bic (int nod,int tt){
int i,vecin;
low[nod]=lvl[nod];
st.push(nod);
for (i=0;i<v[nod].size();i++){
vecin=v[nod][i];
if (vecin==tt)
continue;
if (lvl[vecin]==0){
lvl[vecin]=1+lvl[nod];
dfs_bic(vecin,nod);
low[nod]=min(low[nod],low[vecin]);
if (low[vecin]>=lvl[nod]){ /// nod e un nod critic
bicnx++;
do{
x=st.top();
taken[x]++;
st.pop();
sol[bicnx].insert(x);
}
while (x!=vecin);
sol[bicnx].insert(nod);
taken[nod]++;
/// am scos din stiva muchiile care sunt in subarborele nod->vecin
}
}
else low[nod]=min(low[nod],lvl[vecin]);
}
}
void dfs (int nod){
int sum , i , vecin , tata=0;
//printf ("%d ",nod);
f[nod] = 1;
sum = 0;
if (nod > n){ /// nod
under[nod] = 1;
two[nod] = 0;
}
else { /// componenta
under[nod] = sol[bicnx - nod + 1].size();
x = sol[bicnx - nod + 1].size();
two[nod] = x * (x - 1);
}
for (i = 0 ; i < w[nod].size() ; i++){
vecin = w[nod][i];
if (!f[vecin]){
dfs(vecin);
under[nod] += under[vecin] - 1;
sum += under[vecin];
two[nod] += two[vecin];
}
else tata = vecin;
}
two[nod] = under[nod] * (under[nod] - 1)/2;
//if (nod == 1)
// printf ("a");
if (nod > n){ /// nod
sum = under[nod];
for (i = 0 ; i < w[nod].size() ; i++){
vecin = w[nod][i];
if (vecin != tata){
val = val + 2 * (under[vecin] - 1) * (sum - under[vecin]);
//val = val + two[vecin] - under[vecin] + 1;
}
}
}
else { /// componenta
if (sol[bicnx - nod + 1].size() >= 3){
x = sol[bicnx - nod + 1].size();
val = val + x * (x - 1) * (x - 2);
/// iei 3 din aceeasi comp, CU noduri critice!!!
}
x = sol[bicnx - nod + 1].size();
for (i = 0 ; i < w[nod].size() ; i++){
vecin = w[nod][i];
if (vecin != tata){
/// din subarborele lui vecin iau 2, din alt subarbore iau unul
val = val + 2 * (sum - under[vecin]) * two[vecin];
val = val + 2 * x * ( two[vecin] - under[vecin] );
if (x >= 2){
val = val + 2 * x * (x - 1) * ( under[vecin] - 1 );
}
}
}
}
//printf ("%d %d\n" , nod , val);
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int m , i , x , y , nod;
fscanf (fin,"%d%d",&n,&m);
for (i=1;i<=m;i++){
fscanf (fin,"%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
for (i = 1 ; i <= n ; i++){
if (!lvl[i]){
lvl[i] = 1;
dfs_bic (i , 0);
}
}
/// taken[nod] > 1 => nod critic
for (i = 1 ; i <= bicnx ; i++){
for (set <int> :: iterator it = sol[i].begin() ; it != sol[i].end() ; it++){
nod = *it;
nod += n;
if (taken[nod - n] > 1){
w[nod].push_back(bicnx - i + 1);
w[bicnx - i + 1].push_back(nod);
}
}
}
/// w e arborele componentelor biconexe
/// sau sunt mai multi arbori daca graful nu era conex
for (i = 1 ; i <= bicnx ; i++){
if (!f[i]){
dfs (i);
}
}
fprintf (fout,"%d",val);
return 0;
}
Compilation message
count_triplets.cpp: In function 'void dfs_bic(int, int)':
count_triplets.cpp:14:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs(int)':
count_triplets.cpp:61:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0 ; i < w[nod].size() ; i++){
~~^~~~~~~~~~~~~~~
count_triplets.cpp:84:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0 ; i < w[nod].size() ; i++){
~~^~~~~~~~~~~~~~~
count_triplets.cpp:110:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0 ; i < w[nod].size() ; i++){
~~^~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:139:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d%d",&n,&m);
~~~~~~~^~~~~~~~~~~~~~~~~~
count_triplets.cpp:141:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d%d",&x,&y);
~~~~~~~^~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
11 ms |
12032 KB |
Output is correct |
| 2 |
Correct |
12 ms |
12032 KB |
Output is correct |
| 3 |
Correct |
11 ms |
12160 KB |
Output is correct |
| 4 |
Correct |
11 ms |
12160 KB |
Output is correct |
| 5 |
Correct |
11 ms |
12032 KB |
Output is correct |
| 6 |
Correct |
11 ms |
12032 KB |
Output is correct |
| 7 |
Incorrect |
11 ms |
12160 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
11 ms |
12032 KB |
Output is correct |
| 2 |
Correct |
12 ms |
12032 KB |
Output is correct |
| 3 |
Correct |
11 ms |
12160 KB |
Output is correct |
| 4 |
Correct |
11 ms |
12160 KB |
Output is correct |
| 5 |
Correct |
11 ms |
12032 KB |
Output is correct |
| 6 |
Correct |
11 ms |
12032 KB |
Output is correct |
| 7 |
Incorrect |
11 ms |
12160 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
131 ms |
28664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
12 ms |
12288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
142 ms |
33224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
13 ms |
12288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
134 ms |
33016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
11 ms |
12032 KB |
Output is correct |
| 2 |
Correct |
12 ms |
12032 KB |
Output is correct |
| 3 |
Correct |
11 ms |
12160 KB |
Output is correct |
| 4 |
Correct |
11 ms |
12160 KB |
Output is correct |
| 5 |
Correct |
11 ms |
12032 KB |
Output is correct |
| 6 |
Correct |
11 ms |
12032 KB |
Output is correct |
| 7 |
Incorrect |
11 ms |
12160 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
11 ms |
12032 KB |
Output is correct |
| 2 |
Correct |
12 ms |
12032 KB |
Output is correct |
| 3 |
Correct |
11 ms |
12160 KB |
Output is correct |
| 4 |
Correct |
11 ms |
12160 KB |
Output is correct |
| 5 |
Correct |
11 ms |
12032 KB |
Output is correct |
| 6 |
Correct |
11 ms |
12032 KB |
Output is correct |
| 7 |
Incorrect |
11 ms |
12160 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
