#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int> g[N];
vector<int> bridges[N];
vector<int> notBridges[N];
int add[N], depth[N];
bool vis[N];
vector<vector<int>> cycles;
int getCycle[N];
void dfsAdd(int at, int p) {
vis[at]=1;
for(int to:g[at]) {
if(to==p)continue;
if(vis[to] == 1)
{
if(depth[at] > depth[to]) {
add[at]++;
add[to]--;
notBridges[to].push_back(at);
notBridges[at].push_back(to);
}
continue;
}
depth[to]=depth[at]+1;
dfsAdd(to, at);
}
}
void dfsGetBridges(int at, int p) {
vis[at]=1;
for(int to:g[at]) {
if(vis[to])continue;
dfsGetBridges(to, at);
add[at]+=add[to];
}
if(p==0)return;
if(add[at] == 0) {
bridges[at].push_back(p);
bridges[p].push_back(at);
}
else {
notBridges[at].push_back(p);
notBridges[p].push_back(at);
}
}
vector<int> tempcycle;
void dfsGetCycles(int at) {
tempcycle.push_back(at);
vis[at]=1;
for(int to:notBridges[at]) {
if(vis[to])continue;
dfsGetCycles(to);
}
}
long long dp[N], tmpdp[N];
const long long mod = 1e9+7;
long long ans=0;
void dfsCalc(int c, int cc) {
vis[c]=1;
for(int at:cycles[c]) {
dp[at]=1;
for(int to:g[at]) {
if(!vis[getCycle[to]]) {
dfsCalc(getCycle[to], to);
dp[at] = (dp[at]*(dp[to]+1))%mod;
}
}
}
if(cycles[c].size()==1){
ans+=dp[cycles[c][0]];
ans%=mod;
return;
}
for(int i = 0;i<cycles[c].size();i++) {
long long prod = 1;
int k =i;
int idx=-1, cnt=0;
int sz=0;
while(1) {
sz++;
if(sz == cycles[c].size())break;
if(cycles[c][k] == cc) {
idx=cnt;
}
prod = (prod*dp[cycles[c][k]])%mod;
ans=(ans+prod)%mod;
if(idx != -1) {
tmpdp[cc]=(tmpdp[cc]+prod)%mod;
}
k=(k+1)%cycles[c].size();
}
}
for(int i:cycles[c]) {
dp[i]=tmpdp[i];
}
}
int main () {
cin.tie(0)->sync_with_stdio(0);
int n, m;
cin >> n >> m;
exit(-m);
for(int i = 0;i<m;i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfsAdd(1, 0);
memset(vis, 0, sizeof vis);
dfsGetBridges(1, 0);
memset(vis, 0, sizeof vis);
for(int i = 1;i<=n;i++) {
if(vis[i] == 0) {
dfsGetCycles(i);
for(int c:tempcycle) {
getCycle[c] = cycles.size();
}
cycles.push_back(tempcycle);
tempcycle.clear();
}
}
memset(vis, 0, sizeof vis);
dfsCalc(0, -1);
cout << ans%mod << "\n";
}
Compilation message
Main.cpp: In function 'void dfsCalc(int, int)':
Main.cpp:74:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(int i = 0;i<cycles[c].size();i++) {
| ~^~~~~~~~~~~~~~~~~
Main.cpp:81:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | if(sz == cycles[c].size())break;
| ~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
7256 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
7428 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
7256 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
7256 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
