当前位置:网站首页>poj 2762 Going from u to v or from v to u? (推断它是否是一个薄弱环节图)
poj 2762 Going from u to v or from v to u? (推断它是否是一个薄弱环节图)
2022-07-05 23:01:00 【全栈程序员站长】
大家好,又见面了,我是全栈君
意甲冠军:给定一个有向图有m单向边缘。免费推断是否两点起来(a可以b要么b可以a或最多彼此),该请求
弱联通重量。
算法:
缩点求强连通分量。然后又一次建图。推断新图是否是一条单链,即不能分叉,假设分叉了就会存在不可达的情况。
怎么推断是否是单链呢?
就是每次入度为0的点都仅仅有一个,即每次队列里仅仅有一个点。
( o(╯□╰)o。。。。
。好像已经是第二次用pair记录原图的点对,然后存pair的vector忘记清空导致wa来wa去!
)
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
#define maxn 1010
#define maxm 20010
using namespace std;
struct node
{
int to,next;
}edge[maxm],edge2[maxm];
int head[maxn],cnt,n;
int clk,top,s[maxn],scc,dfn[maxn],low[maxn],belong[maxn];
bool instack[maxn],vis[maxn];
int head2[maxn],cnt2,in[maxn];
typedef pair<int,int> PII;
vector<PII> xx;
queue<int> q;
void add(int x,int y)
{
edge[cnt].to = y;
edge[cnt].next = head[x];
head[x] = cnt++;
}
void add2(int x,int y)
{
edge2[cnt2].to = y;
edge2[cnt2].next = head2[x];
head2[x] = cnt2++;
}
void dfs(int x)
{
dfn[x] = low[x] = clk++;
s[top++] = x;
instack[x] = true;
for(int i=head[x];i!=-1;i = edge[i].next)
{
int u = edge[i].to;
if(dfn[u]==-1)
{
dfs(u);
low[x] = min(low[u],low[x]);
}
else if(instack[u])
{
low[x] = min(low[x],dfn[u]);
}
}
if(low[x]==dfn[x])
{
int u;
scc++;
do
{
u = s[--top];
instack[u]=false;
belong[u] = scc;
}while(u!=x);
}
}
void tarjan()
{
memset(dfn,-1,sizeof(dfn));
memset(instack,0,sizeof(instack));
memset(belong,0,sizeof(belong));
clk = top = scc = 0;
for(int i=1;i<=n;i++)
{
if(dfn[i]==-1)
dfs(i);
}
}
bool topo()
{
memset(vis,0,sizeof(vis));
int c = 0;
while(!q.empty())
q.pop();
for(int i=1;i<=scc;i++)
{
if(!in[i])
{
c++;
q.push(i);
}
}
if(c>1) return false;
while(!q.empty())
{
int u = q.front();
q.pop();
if(vis[u]) continue;
vis[u] = true;
c = 0;
for(int i=head2[u];i!=-1;i=edge2[i].next)
{
int v = edge2[i].to;
in[v]--;
if(!in[v])
{
q.push(v);
c++;
}
}
if(c>1)
return false;
}
return true;
}
int main()
{
int m,a,b,T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
memset(head,-1,sizeof(head));
memset(in,0,sizeof(in));
xx.clear();
cnt = 0;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
add(a,b);
xx.push_back(make_pair(a,b));
}
tarjan();
memset(head2,-1,sizeof(head2));
cnt2 = 0;
for(int i=0;i<xx.size();i++)
{
int u = xx[i].first,v = xx[i].second;
if(belong[u]!=belong[v])
{
add2(belong[u],belong[v]);
in[belong[v]]++;
}
}
if(topo()) printf("Yes\n");
else printf("No\n");
}
return 0;
}
版权声明:本文博客原创文章,博客,未经同意,不得转载。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/117526.html原文链接:https://javaforall.cn
边栏推荐
- fibonacci search
- 东南亚电商指南,卖家如何布局东南亚市场?
- Alibaba Tianchi SQL training camp task4 learning notes
- CJ mccullem autograph: to dear Portland
- CorelDRAW plug-in -- GMS plug-in development -- new project -- macro recording -- VBA editing -- debugging skills -- CDR plug-in (2)
- Common model making instructions
- Matlab smooth curve connection scatter diagram
- Use of metadata in golang grpc
- openresty ngx_lua请求响应
- 一文搞定class的微观结构和指令
猜你喜欢
Three. Js-01 getting started
Element operation and element waiting in Web Automation
Expectation, variance and covariance
Commonly used probability distributions: Bernoulli distribution, binomial distribution, polynomial distribution, Gaussian distribution, exponential distribution, Laplace distribution and Dirac delta d
YML configuration, binding and injection, verification, unit of bean
2022 registration examination for safety management personnel of hazardous chemical business units and simulated reexamination examination for safety management personnel of hazardous chemical busines
Tensor attribute statistics
Dynamic memory management (malloc/calloc/realloc)
Douban scoring applet Part-2
Thoroughly understand JVM class loading subsystem
随机推荐
2022 registration examination for safety management personnel of hazardous chemical business units and simulated reexamination examination for safety management personnel of hazardous chemical busines
Metasploit (MSF) uses MS17_ 010 (eternal blue) encoding:: undefined conversionerror problem
【Note17】PECI(Platform Environment Control Interface)
第十七周作业
一文搞定JVM的内存结构
(4)UART應用設計及仿真驗證2 —— TX模塊設計(無狀態機)
Alibaba Tianchi SQL training camp task4 learning notes
[speech processing] speech signal denoising and denoising based on Matlab GUI low-pass filter [including Matlab source code 1708]
Douban scoring applet Part-2
What is the process of building a website
[speech processing] speech signal denoising based on Matlab GUI Hanning window fir notch filter [including Matlab source code 1711]
LeetCode102. Sequence traversal of binary tree (output by layer and unified output)
openresty ngx_lua正则表达式
Un article traite de la microstructure et des instructions de la classe
UART Application Design and Simulation Verification 2 - TX Module Design (Stateless machine)
数据库基础知识(面试)
audiopolicy
Use of shell:for loop
二叉树递归套路总结
东南亚电商指南,卖家如何布局东南亚市场?