洛谷 P2341 [HAOI2006]受欢迎的牛|【模板】强连通分量
2024-10-08 14:30:29
题目传送门
解题思路:
先求强联通分量,缩点,然后统计新图中有几个点出度为0,如果大于1个,则说明这不是一个连通图,答案即为0.否则入度为0的那个强连通分量的点数即为答案
AC代码:
#include<iostream>
#include<cstdio>
#include<stack>
#include<set> using namespace std; int daan,n,m,head[],tot;
int dfn[],low[],sum,rp;
int belong[],_head[],num[];
bool vis[];
struct kk{
int to,next;
}e[],a[];
stack<int> s;
set<int> ans[]; inline void add(int x,int y) {
e[++tot].to = y;
e[tot].next = head[x];
head[x] = tot;
} inline void tarjan(int x) {
dfn[x] = low[x] = ++sum;
int v;
s.push(x);
vis[x] = ;
for(int i = head[x];i != ; i = e[i].next) {
v = e[i].to;
if(!dfn[v]) {
tarjan(v);
low[x] = min(low[x],low[v]);
}
else if(vis[x])
low[x] = min(low[x],dfn[v]);
}
if(dfn[x] == low[x]) {
rp++;
do {
v = s.top();
s.pop();
belong[v] = rp;
num[rp]++;
vis[x] = false;
}
while(v != x);
}
} inline void _add(int x,int y) {
a[++tot].to = y;
a[tot].next = _head[x];
_head[x] = tot;
} inline void findin() {
for(int i = ;i <= rp; i++)
for(int j = _head[i];j != ; j = a[j].next) {
int o = a[j].to;
ans[i].insert(o);
}
} int main() {
scanf("%d%d",&n,&m);
for(int i = ;i <= m; i++) {
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
}
for(int i = ;i <= n; i++)
if(!dfn[i]) //求强连通分量
tarjan(i);
tot = ;
for(int i = ;i <= n; i++)//构建新图,其实没啥必要
for(int j = head[i];j != ; j = e[j].next)
if(belong[i] != belong[e[j].to])
_add(belong[i],belong[e[j].to]);
findin();
for(int i = ;i <= rp; i++)//找入度为0的点
if(ans[i].size() == ) {
if(daan != ) {
printf("");
return ;
}
daan = i;
}
printf("%d",num[daan]);
return ;
}
第一次的做法,用了set,较麻烦
#include<iostream>
#include<cstdio>
#include<stack>
#include<set> using namespace std; int daan,n,m,head[],tot;
int _out[],dfn[],low[];
int sum,rp,belong[];
int _head[],num[];
bool vis[];
struct kk{
int to,next;
}e[],a[];
stack<int> s; inline void add(int x,int y) {
e[++tot].to = y;
e[tot].next = head[x];
head[x] = tot;
} inline void tarjan(int x) {
dfn[x] = low[x] = ++sum;
int v;
s.push(x);
vis[x] = ;
for(int i = head[x];i != ; i = e[i].next) {
v = e[i].to;
if(!dfn[v]) {
tarjan(v);
low[x] = min(low[x],low[v]);
}
else if(vis[x])
low[x] = min(low[x],dfn[v]);
}
if(dfn[x] == low[x]) {
rp++;
do {
v = s.top();
s.pop();
belong[v] = rp;
num[rp]++;
vis[x] = false;
}
while(v != x);
}
} inline void _add(int x,int y) {
a[++tot].to = y;
a[tot].next = _head[x];
_head[x] = tot;
} int main() {
scanf("%d%d",&n,&m);
for(int i = ;i <= m; i++) {
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
}
for(int i = ;i <= n; i++)
if(!dfn[i])
tarjan(i);
tot = ;
for(int i = ;i <= n; i++)
for(int j = head[i];j != ; j = e[j].next)
if(belong[i] != belong[e[j].to])
_out[belong[i]]++;
for(int i = ;i <= rp; i++)
if(_out[i] == ) {
if(daan != ) {
printf("");
return ;
}
daan = i;
}
printf("%d",num[daan]);
return ;
}
改进后的代码,发现不用set,比较精简
最新文章
- kvm 性能调优
- php给一张图片加上水印效果
- C#时间格式之GMT时间的格式
- 获取FMS的状态信息
- chkconfig命令(管理开机自启)
- Vuejs——v-on
- JavaScript 轮播图实例
- 浅析redis缓存 在spring中的配置 及其简单的使用
- 『最长等差数列 线性DP』
- HTML学习笔记01(标签)
- 为什么要用docker
- Flask序列化
- Learning-Python【34】:进程之生产者消费者模型
- django 正向,反向
- Excel 常用设置
- Json中不支持任何形式的注释,那我们要怎么解决呢
- command not found Operation not permitted
- 在JavaScript文件中用ajax方法实现省市区的三级联动
- Volley源码分析(五)Volley源码总结篇
- 【C++】STL常用容器总结之五:双端队列deque