#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define PB push_back
#define MP make_pair
//Union-Find木(サイズ有り)
struct UnionFind{
private:
vector<int> parent;
vector<int> size;
public:
void init(int N){ //初期化する O(N)
parent.clear();
size.clear();
for(int i=0; i<N; i++) parent.push_back(i);
for(int i=0; i<N; i++) size.push_back(1);
}
int root(int a){ //親を返す O(log N)
if(parent[a] == a) return a;
return parent[a] = root(parent[a]);
}
void unite(int a, int b){ //木を併合する O(log N)
int rootA = root(a);
int rootB = root(b);
if(rootA == rootB) return;
if(size[rootA] < size[rootB]){
parent[rootA] = rootB;
size[rootB] += size[rootA];
size[rootA] = 0;
}
else{
parent[rootB] = rootA;
size[rootA] += size[rootB];
size[rootB] = 0;
}
}
bool same(int a, int b){ //属する木が同じかを返す O(log N)
return root(a) == root(b);
}
long long culcSize(int a){ //属する木の要素数を返す O(log N)
return size[root(a)];
}
void decrement(int a, int x){
a = root(a);
size[a] -= x;
}
};
LL N, M;
vector<int> edge[100000];
vector<bool> canUse[100000];
int sz[100000];
int pre[100000]={}, low[100000];
int c = 0;
vector<pair<int, int>> bridge;
UnionFind fact;
int dfs(int now, int par, int idx){
if(pre[now] != 0) return pre[now];
if(par != -1) fact.unite(now, par);
pre[now] = c; c++;
low[now] = pre[now];
for(int i=0; i<edge[now].size(); i++){
if(edge[now][i] == par) continue;
low[now] = min(low[now], dfs(edge[now][i], now, i));
}
if(low[now] == pre[now] && par != -1){
bridge.PB(MP(now, par));
canUse[par][idx] = false;
for(int i=0; i<edge[now].size(); i++)
if(edge[now][i] == par) canUse[now][i] = false;
}
return low[now];
}
UnionFind uf;
bool flg[100000] ={};
void bfs(int now){
if(flg[now]) return;
queue<int> que;
que.push(now);
flg[now] = false;
while(!que.empty()){
int now = que.front();
que.pop();
for(int i=0; i<edge[now].size(); i++){
if(!canUse[now][i]){
continue;
}
if(flg[edge[now][i]]) continue;
uf.unite(now, edge[now][i]);
flg[edge[now][i]] = true;
que.push(edge[now][i]);
}
}
}
set<int> newEdge[100000];
int main(){
cin >> N >> M;
for(int i=0; i<M; i++){
int a, b;
cin >> a >> b;
edge[a-1].PB(b-1);
canUse[a-1].PB(true);
edge[b-1].PB(a-1);
canUse[b-1].PB(true);
}
for(int i=0; i<N; i++) sz[i] = edge[i].size();
//橋の検出
for(int i=0; i<N; i++) low[i] = INT_MAX;
fact.init(N);
for(int i=0; i<N; i++) dfs(i,-1,-1);
//二重辺連結成分分解(オリジナル実装)
uf.init(N);
for(int i=0; i<N; i++) bfs(0);
for(int i=0; i<N; i++){
for(int j=0; j<edge[i].size(); i++){
if(!uf.same(i, edge[i][j])){
newEdge[uf.root(i)].insert(uf.root(edge[i][j]));
newEdge[uf.root(edge[i][j])].insert(uf.root(i));
}
}
}
//葉の検出
queue<int> que;
for(int i=0; i<N; i++){
if(uf.root(i) != i) continue;
if(newEdge[i].size() == 1) que.push(i);
}
//答えの計算
LL ans = 0;
while(!que.empty()){
int now = que.front();
que.pop();
if(newEdge[now].size() == 0) continue;
LL tmp = fact.culcSize(now) - uf.culcSize(now);
ans += tmp * uf.culcSize(now) * (tmp-1);
fact.decrement(now, uf.culcSize(now));
int idx = *newEdge[now].begin();
newEdge[now].erase(idx);
newEdge[idx].erase(now);
if(newEdge[idx].size() == 1) que.push(idx);
}
cout << ans << endl;
}
Compilation message
count_triplets.cpp: In function 'int dfs(int, int, int)':
count_triplets.cpp:64:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<edge[now].size(); i++){
~^~~~~~~~~~~~~~~~~
count_triplets.cpp:71:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<edge[now].size(); i++)
~^~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void bfs(int)':
count_triplets.cpp:87:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<edge[now].size(); i++){
~^~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:123:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0; j<edge[i].size(); i++){
~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
11392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
11392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
286 ms |
31600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
11420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
291 ms |
56092 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
11392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
327 ms |
56160 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
11392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
11392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
