当前位置:网站首页>poj 2762 Going from u to v or from v to u? (infer whether it is a weak link diagram)
poj 2762 Going from u to v or from v to u? (infer whether it is a weak link diagram)
2022-07-05 23:16:00 【Full stack programmer webmaster】
Hello everyone , I meet you again , I'm the king of the whole stack
Serie A Champion : Given a digraph has m Unidirectional edge . Free inference whether two points up (a Sure b or b Sure a Or at most each other ), The request
Weak connection weight .
Algorithm :
Shrink the point to find the strongly connected component . Then build the map again . Infer whether the new graph is a single chain , That is, you can't fork , If it forks, there will be inaccessible situations .
How to infer whether it is a single chain ?
It means that each entry is 0 There is only one point , That is, there is only one point in the queue each time .
( o(╯□╰)o....
. It seems to have been used for the second time pair Record the point pairs of the original drawing , Then save pair Of vector Forgetting to empty leads to wa Come on wa Go to !
)
#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;
}
Copyright notice : This article is an original blog article , Blog , Without consent , Shall not be reproduced .
Publisher : Full stack programmer stack length , Reprint please indicate the source :https://javaforall.cn/117526.html Link to the original text :https://javaforall.cn
边栏推荐
- One article deals with the microstructure and instructions of class
- LeetCode145. Post order traversal of binary tree (three methods of recursion and iteration)
- 14种神笔记方法,只需选择1招,让你的学习和工作效率提高100倍!
- Hcip day 12 (BGP black hole, anti ring, configuration)
- (4)UART应用设计及仿真验证2 —— RX模块设计(无状态机)
- Initial experience | purchase and activate typora software
- Leetcode buys and sells stocks
- Use of shell:for loop
- 如何快速理解复杂业务,系统思考问题?
- C Primer Plus Chapter 9 question 9 POW function
猜你喜欢
Selenium+Pytest自动化测试框架实战
MoCo: Momentum Contrast for Unsupervised Visual Representation Learning
[speech processing] speech signal denoising and denoising based on MATLAB low-pass filter [including Matlab source code 1709]
Hcip day 11 (BGP agreement)
数学公式截图识别神器Mathpix无限使用教程
Sum of two numbers, sum of three numbers (sort + double pointer)
Leetcode weekly The 280 game of the week is still difficult for the special game of the week's beauty team ~ simple simulation + hash parity count + sorting simulation traversal
Creative mode 1 - single case mode
Using LNMP to build WordPress sites
Go语言实现原理——锁实现原理
随机推荐
3D reconstruction of point cloud
Go语言实现原理——Map实现原理
golang代码检查工具
The maximum happiness of the party
Krypton Factor purple book chapter 7 violent solution
Shell: operator
AsyncSocket长连接棒包装问题解决
February 13, 2022-4-symmetric binary tree
Roman numeral to integer
PLC编程基础之数据类型、变量声明、全局变量和I/O映射(CODESYS篇 )
[untitled]
2022 registration examination for safety management personnel of hazardous chemical business units and simulated reexamination examination for safety management personnel of hazardous chemical busines
14种神笔记方法,只需选择1招,让你的学习和工作效率提高100倍!
It is proved that POJ 1014 module is optimized and pruned, and some recursion is wrong
基于脉冲神经网络的物体检测
From the perspective of quantitative genetics, why do you get the bride price when you get married
2.13 summary
Go language implementation principle -- lock implementation principle
证明 poj 1014 模优化修剪,部分递归 有错误
终于搞懂什么是动态规划的