POJ 2186 强联通分量
2024-08-25 13:59:25
题意:牛A喜欢牛B,若牛B喜欢牛C,则牛A喜欢牛C,问最后多少牛被其它全部牛喜欢
思路:用强联通分量进行缩点,最后形成的图是有向无环图DAG。而拓扑序的值为DAG的长度,则加一,可是最后我们要推断一下这些牛是不是被全部牛喜欢,由于等于DAG长度的全部点肯定是一个强联通分量,因此它们能够相互喜欢,我们用当中一仅仅牛推断即可了,推断时就用反向边推断这个牛能不能到达其它的牛即可了
#include <vector>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=10010;
int V;
vector<int>G[maxn];
vector<int>rG[maxn];
vector<int>vs;
bool used[maxn];
int cmp[maxn];
void add_edge(int from,int to){
G[from].push_back(to);
rG[to].push_back(from);
}
void dfs(int v){
used[v]=1;
for(unsigned int i=0;i<G[v].size();i++){
if(!used[G[v][i]]) dfs(G[v][i]);
}
vs.push_back(v);
}
void rdfs(int v,int k){
used[v]=1;
cmp[v]=k;
for(unsigned int i=0;i<rG[v].size();i++){
if(!used[rG[v][i]]) rdfs(rG[v][i],k);
}
}
int scc(){
memset(used,0,sizeof(used));
vs.clear();
for(int v=0;v<V;v++){
if(!used[v]) dfs(v);
}
memset(used,0,sizeof(used));
int sum=0;
for(int i=vs.size()-1;i>=0;i--){
if(!used[vs[i]]) rdfs(vs[i],sum++);
}
return sum;
}
int main(){
int m;
while(scanf("%d%d",&V,&m)!=-1){
for(int i=0;i<maxn;i++) G[i].clear();
for(int j=0;j<maxn;j++) rG[j].clear();
int a,b;
for(int i=0;i<m;i++){
scanf("%d%d",&a,&b);
add_edge(a-1,b-1);
}
int t=scc(),ans=0,pos;
for(int i=0;i<V;i++){
if(cmp[i]==t-1){
ans++;
pos=i;
}
}
memset(used,0,sizeof(used));
rdfs(pos,0);
for(int i=0;i<V;i++){
if(used[i]==0){
ans=0;break;
}
}
printf("%d\n",ans);
}
return 0;
}
最新文章
- Form authentication(表单认证)问题
- Java中synchronized详解
- 纸上谈兵:AVL树
- xcode6.0 模拟器打不开
- ios5 中文键盘高度变高覆盖现有ui问题的解决方案(获取键盘高度的方法)(转载)
- setTimeout、clearTimeout、setInterval,clearInterval ——小小计时器
- DM8168 坎坷硬件之路(DDR3)
- 中国大学MOOC-翁恺-C语言程序设计习题集
- Android 显示YUV编码格式
- DICOM医学图像处理:DCMTK在VS2012中的配置
- iOS 程序间跳转传参(支付和地图)
- SecureCRT 密钥生成 SSH 使用密钥登陆 服务器
- [html]关于html标签的一些总结
- jmeter返回的post data乱码
- c# MongoDB Driver 官方教程翻译
- 【论文速读】Chuhui Xue_ECCV2018_Accurate Scene Text Detection through Border Semantics Awareness and Bootstrapping
- Runtime ";Apache Tomcat v6.0 (3)"; is invalid. The JRE could not be found. Edit the server and change the JRE location解决方案
- Django深度剖析-二
- CSS3常用功能的写法 转
- VUE设置浏览器icon图标