This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const long long maxn = 2e5 + 12, mod = 1e9 + 7;
long long n, m, pd[maxn], h[maxn], dp[maxn], sum[maxn];
vector <int> conn[maxn], nums;
bitset <maxn> marked, in_nums;
void dfs(int u, int p = -1){
marked[u] = 1;
int me = -1;
for(int v: conn[u])
if(!marked[v]){
pd[v] = u;
h[v] = h[u] + 1;
dfs(v, u);
}
else if(h[u] < h[v])
me = v;
// cout << u << ' ' << me << endl;
if(me == -1){
dp[u] = 1;
for(int v: conn[u])
if(h[u] < h[v]){
// cout << u << '-' << v << endl;
dp[u] = (dp[u] * (dp[v] + 1)) % mod;
}
dp[u] %= mod;
//cout << u << "->" << dp[u] << endl;
}
else{
nums.clear();
in_nums = 0;
while(h[u] <= h[me] && me){
nums.push_back(me);
in_nums[me] = 1;
me = pd[me];
}
for(int j = 0; j <= nums.size(); j++)
sum[j] = 0;
long long res = 1;
for(int j = 0; j < nums.size(); j++){
int nu = nums[j];
for(int v: conn[nu])
if(h[nu] < h[v] && !in_nums[v]){
res = res * (dp[v] + 1) % mod;
res %= mod;
}
sum[j] = (j == 0? 1: sum[j - 1]);
sum[j] += res;
sum[j] %= mod;
// cout << nu << ' ' << sum[j] << endl;
}
// cout << dp[2] << endl;
res = 1;
for(int j = nums.size() - 1; j >= 1; j--){
int nu = nums[j];
for(int v: conn[nu])
if(h[nu] < h[v] && !in_nums[v]){
res = res * (dp[v] + 1) % mod;
}
res %= mod;
if(j - 2 >= 0)
dp[u] += res % mod * (sum[j - 2] % mod) % mod;
dp[u] %= mod;
}
//cout << dp[2] << endl;
dp[u] += res;
dp[u] %= mod;
}
}
int main(){
cin >> n >> m;
for(int i = 0; i < m; i++){
int a, b;
cin >> a >> b;
conn[a].push_back(b);
conn[b].push_back(a);
}
// cout << endl;
dfs(1);
long long ans = 0;
// cout << endl;
for(int i = 1; i <= n; i++){
ans += dp[i];
ans %= mod;
// cout << i << ' ' << dp[i] << endl;
}
cout << ans << endl;
}
/* cin >> n >> m;
for(int i = 0; i < m; i++){
int a, b;
cin >> a >> b;
e[a][b] = 1;
e[b][a] = 1;
}
int ans = 0;
cout << endl;
for(int i = 0; i < (1 << n); i++){
for(int j = 0; j < n; j++)
if((i >> j) & 1)
p.push_back(j + 1);
int num = 0;
for(int j = 0; j < p.size(); j++)
for(int c = j; c < p.size(); c++)
if(e[p[j]][p[c]])
num += 1;
if(num == p.size() - 1){
if(p[0] == 1){
for(int j: p)
cout << j << ' ';
cout << endl;
}
ans += 1;
}
p.clear();
}
cout << ans << endl;
*/
Compilation message (stderr)
Main.cpp: In function 'void dfs(int, int)':
Main.cpp:40:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for(int j = 0; j <= nums.size(); j++)
| ~~^~~~~~~~~~~~~~
Main.cpp:43:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int j = 0; j < nums.size(); j++){
| ~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |