dfs找环
2024-09-05 01:27:49
http://acm.hdu.edu.cn/showproblem.php?pid=6736
Forest Program
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 299 Accepted Submission(s): 111
Problem Description
The
kingdom of Z is fighting against desertification these years since
there are plenty of deserts in its wide and huge territory. The deserts
are too arid to have rainfall or human habitation, and the only
creatures that can live inside the deserts are the cactuses. In this
problem, a cactus in desert can be represented by a cactus in graph
theory.
In graph theory, a cactus is a connected undirected graph
with no self-loops and no multi-edges, and each edge can only be in at
most one simple cycle. While a tree in graph theory is a connected
undirected acyclic graph. So here comes the idea: just remove some edges
in these cactuses so that the remaining connected components all become
trees. After that, the deserts will become forests, which can halt
desertification fundamentally.
Now given an undirected graph with n
vertices and m edges satisfying that all connected components are
cactuses, you should determine the number of schemes to remove edges in
the graph so that the remaining connected components are all trees.
Print the answer modulo 998244353.
Two schemes are considered to be different if and only if the sets of removed edges in two schemes are different.
kingdom of Z is fighting against desertification these years since
there are plenty of deserts in its wide and huge territory. The deserts
are too arid to have rainfall or human habitation, and the only
creatures that can live inside the deserts are the cactuses. In this
problem, a cactus in desert can be represented by a cactus in graph
theory.
In graph theory, a cactus is a connected undirected graph
with no self-loops and no multi-edges, and each edge can only be in at
most one simple cycle. While a tree in graph theory is a connected
undirected acyclic graph. So here comes the idea: just remove some edges
in these cactuses so that the remaining connected components all become
trees. After that, the deserts will become forests, which can halt
desertification fundamentally.
Now given an undirected graph with n
vertices and m edges satisfying that all connected components are
cactuses, you should determine the number of schemes to remove edges in
the graph so that the remaining connected components are all trees.
Print the answer modulo 998244353.
Two schemes are considered to be different if and only if the sets of removed edges in two schemes are different.
Input
The
first line contains two non-negative integers n, m (1 ≤ n ≤ 300 000, 0 ≤
m ≤ 500 000), denoting the number of vertices and the number of edges
in the given graph.
Next m lines each contains two positive integers
u, v (1 ≤ u, v ≤ n, u = v), denoting that vertices u and v are connected
by an undirected edge.
It is guaranteed that each connected component in input graph is a cactus.
first line contains two non-negative integers n, m (1 ≤ n ≤ 300 000, 0 ≤
m ≤ 500 000), denoting the number of vertices and the number of edges
in the given graph.
Next m lines each contains two positive integers
u, v (1 ≤ u, v ≤ n, u = v), denoting that vertices u and v are connected
by an undirected edge.
It is guaranteed that each connected component in input graph is a cactus.
Output
Output a single line containing a non-negative integer, denoting the answer modulo 998244353.
Sample Input
3 3
1 2
2 3
3 1
6 6
1 2
2 3
3 1
2 4
4 5
5 2
1 2
2 3
3 1
6 6
1 2
2 3
3 1
2 4
4 5
5 2
Sample Output
7
49
49
Source
Recommend
//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdio.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string.h>
#include <vector>
#define ME(x , y) memset(x , y , sizeof(x))
#define SF(n) scanf("%d" , &n)
#define rep(i , n) for(int i = 0 ; i < n ; i ++)
#define INF 0x3f3f3f3f
#define mod 998244353
#define PI acos(-1)
using namespace std;
typedef long long ll ;
const int maxn = ;
const int maxm = ;
ll n , m , sum , ans , vis[maxn] , dfn[maxn] , cnt;
ll head[maxn];
struct Edge
{
ll to , next ;
}e[maxm]; void add(ll u , ll v)
{
e[cnt].to = v ;
e[cnt].next = head[u];
head[u] = cnt++;
} void init()
{
memset(vis , , sizeof(vis));
memset(dfn , , sizeof(dfn));
memset(head , - , sizeof(head));
cnt = , ans = ;
}
ll qpow(ll base, ll n)
{
ll ans = ;
while(n)
{
if(n&) ans=(ans%mod)*(base%mod)%mod;
base = (base%mod) * (base%mod)%mod;
n/=;
}
return ans%mod;
} void dfs(ll id , ll step , ll fa)
{
vis[id] = , dfn[id] = step ;
for(ll i = head[id] ; i != - ; i = e[i].next)
{
ll v = e[i].to ;
//cout << i << " " << v << endl ;
if(v == fa || vis[v] == ) continue ;
if(vis[v] == )
{
sum += step - dfn[v] + ;
ans *= (qpow( , step-dfn[v]+)-+mod) % mod ;
ans %= mod ;
}
else
{
dfs(v , step+ , id);
}
}
vis[id] = ;
} int main()
{
scanf("%lld%lld" , &n , &m);
init();
for(ll i = ; i <= m ; i++)
{
ll u , v ;
scanf("%lld%lld" , &u , &v);
add(u , v);
add(v , u);
}
for(ll i = ; i <= n ; i++)
{
if(!vis[i])
dfs(i , , -);
}
ans *= qpow( , m - sum);
ans %= mod ;
printf("%lld\n" , ans); return ;
}
最新文章
- 关于linux,我们应该学什么?
- jQuery的getText()方法源码
- PHP面向对象(分页)
- firefox查看微信公众平台的数据分析时就出现不信任链接怎么办?
- Codevs 1222 信与信封问题 二分图匹配,匈牙利算法
- BestCoder Round #38
- pip install 出现报asciii码错误的解决
- 201521123016 《Java程序设计》第7周学习总结
- kettle文件自动化部署(shell脚本执行):命令行参数传入
- Tihinkphp3.2整合最新版阿里大鱼进行短信验证码发送
- Spring Boot2.0 设置拦截器
- Spring Cloud 微服务中搭建 OAuth2.0 认证授权服务
- numpy random
- Voltage Translation for Analog to Digital Interface ADC
- elasticSearch6源码分析(6)http和transport模块
- mfc 类模板
- php重新整理数组索引
- Java常见的乱码解决方式
- springboot-8- 日志配置
- Golang报错mixture of field:value and value initializers
热门文章
- CTF Jarvisoj Web(session.upload_progress.name php 上传进度)
- Windows Server2008R2蓝屏,分析dmp文件
- 【LuoguP3747】[六省联考2017] 相逢是问候
- Arduino-位操作
- 《SaltStack技术入门与实践》—— Event和Reactor系统
- mysql AND运算符 语法
- HDU 5687 Problem C ( 字典树前缀增删查 )
- Activiti流量变量(九)
- Leetcode 8. String to Integer (atoi)(模拟题,水)
- 使用visual studio配置和运行《opengl圣经》的第一个案例