Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5400    Accepted Submission(s): 2411

Problem Description
In order to train Xiao Xi's sense of direction ,Gardon Built a big castle , There are N A room (N<=10000) and M Channels (M<=100000), Each channel is unidirectional , That is to say, if a channel is connected A Room and B room , It only means that you can pass through this channel by A The room arrived B room , But it doesn't mean that it can be used by B The room arrived A room .Gardon Please write a program to confirm whether any two rooms are interconnected , namely : For arbitrary i and j, There is at least one path from the room i To the room j, There is also a path from the room j To the room i.
 
Input
The input contains multiple sets of data , The first line of input has two numbers :N and M, Next M Each row has two numbers a and b, Represents a channel that can be accessed from A The room came B room . The document ends with two 0 end .
 
Output
For each set of data entered , If any two rooms are interconnected , Output "Yes", Otherwise output "No".
 
Sample Input
3 3
1 2
2 3
3 1
3 3
1 2
2 3
3 2
0 0
 
Sample Output
Yes
No
 
The meaning of the question is very clear , Is to determine whether a digraph is strongly connected , That is, whether any two points in the graph can reach each other ;
New learning tarjan Algorithm , The understanding is not very thorough , Referring to the pseudo code and the code of the great God, knock ;
 #include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std; vector<int>edge[];// Use adjacency table to store graph ;
int n,m;
int dfn[];// Depth first search access order , Record u The number of steps visited for the first time ;
int low[];// The earliest order that can be traced back ;
int st[];//tarjan The stack in ;
int din; // Reference no. ;
int num; // The number of strongly connected components ;
int top; // The number of elements in the stack ;
int in[];// Whether it's on the stack ; void tarjan(int u)
{
int i,j;
int v;
dfn[u] = low[u] = ++din;// For the node u Set the access number ;
in[u] = ;
st[++top] = u;// Pressure into the stack
for(i = ; i < edge[u].size(); i++)// Traversal and u Connected nodes
{
v = edge[u][i];
if(!dfn[v])// If node v Not visited
{
tarjan(v);// Continue down
low[u] = min(low[u],low[v]);
}
else if(in[v])// If node v Has been interviewed , And it's on the stack
{
low[u] = min(low[u],dfn[v]);
}
} if(dfn[u] == low[u])// If node u Is the root of a strongly connected component
{
num++;// The number of connected components plus 1;
do
{
j = st[top--];
in[j] = ;
}
while(j != u);// The nodes in the strongly connected component are de stack ,
} }
void init()
{
int i;
memset(dfn,,sizeof(dfn));
top = ;
num = ;
din = ;
for(i = ; i <= n; i++)
{
if(!dfn[i])
{
tarjan(i);
}
} }
int main()
{
int u,v;
while(~scanf("%d %d",&n,&m))
{
if(n == && m == )
break;
for(int i = ; i <= n; i++)
edge[i].clear();
while(m--)
{
scanf("%d %d",&u,&v);
edge[u].push_back(v);
}
init();
if(num == )
printf("Yes\n");
else printf("No\n");
}
return ;
}

The sample code

?

tarjan(u)

{
DFN[u]=Low[u]=++Index // For the node u Set the sequence number and Low initial value
Stack.push(u) // The nodes u Pressure into the stack
foreach (u, v)in E // Enumerate every edge
if(v is not visted) // If node v Not visited
tarjan(v) // Keep looking down
Low[u]= min(Low[u], Low[v])
elseif(v in S) // If node v It's still in the stack
Low[u]= min(Low[u], DFN[v])
if(DFN[u]== Low[u]) // If node u Is the root of a strongly connected component
repeat
v = S.pop // take v Backstack , Is a vertex of the strongly connected component
print v
until (u== v)
}

HDOJ Labyrinth castle ( Judge strong connectivity tarjan Algorithm ) More articles about

  1. hdu1269 Labyrinth castle ( Determine whether a digraph is a strongly connected graph )

    1 /* The question : Here's a picture for you , Let's see if the directed graph is a strongly connected graph ( Every two nodes can reach each other )! Ideas 1: Press the positive side dfs Again , Count the number of nodes passing through , If the number of nodes recorded is less than n, So the graph is not connected according to the positive edge ...

  2. HDU 1269 Labyrinth castle ( Strong connected components , routine )

    The question : Judge whether the given digraph is a strongly connected graph . Ideas : If the connected component is greater than 1 Then it must be No, If the strongly connected component is greater than 1 It's also No.tarjan Algorithm for strong connected components . #include <cstdio> #in ...

  3. 【 Algorithm • Day watch • Issue 28 】 graph theory : Strong connectivity +Tarjan Algorithm ( One )

    ▎ Preface I always want to learn this thing , I thought it was hard , It turns out that's all . As long as you know the basis of graph theory . ▎ Strong connectivity *『 Definition 』 Since it's called strong connectivity , So it must be very connected . Strong connectivity : In a digraph , Two vertices can interact with each other ...

  4. HDU 1269 Labyrinth castle ( Strong connectivity )

    HDU 1269 Labyrinth castle pid=1269" target="_blank" style=""> Topic link The question : Chinese questions Ideas : Strongly connected template problem generation ...

  5. CF:Problem 427C - Checkposts Strong connectivity Tarjan Algorithm

    tarjan Algorithm number one Spray me on the face . ... Turn the type of handwriting stack to BOOL. I've been looking for mistakes .. . #include<cstdio> #include<cstring> #includ ...

  6. HDU 1269: Labyrinth castle ( Strong connectivity )

    http://acm.hdu.edu.cn/showproblem.php?pid=1269 The question : Determine whether it is a strongly connected graph . Ideas : Naked tarjan Algorithm . #include <cstdio> ...

  7. HDU 1269 Labyrinth castle ( Determine the number of strongly connected components of a digraph ,tarjan Algorithm )

    Labyrinth castle Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submis ...

  8. HDU 1269 Labyrinth castle tarjan Algorithm for strong connected components

    Basic template questions , application tarjan Algorithm for strong connected components of digraph ,tarjan The implementation here is : Use the stack to store points that have been accessed , When the point of access leaves dfs When , Judging this point is low Whether the value equals its date of birth dfn value , If equal , ...

  9. 【 Strong connectivity graph | Strong connection component 】HDU 1269 Labyrinth castle 【Kosaraju or Tarjan Algorithm 】

      In order to train Xiao Xi's sense of direction ,Gardon Built a big castle , There are N A room (N<=10000) and M Channels (M<=100000), Each channel is unidirectional , That is to say, if a channel is connected A Room and B room , Just say ...

Random recommendation

  1. Bugtags Introduction video - App test &#183; Never so simple

    Bugtags What is it? ? Bugtags It's the first choice in the mobile age Bug Management system , For different use scenarios ,Bugtags It has the following powerful features : Mobile application Bug management Bugtags It can be directly applied in WYSIWYG ...

  2. Spring Cache annotations @Cache Use

    Reference material http://www.ibm.com/developerworks/cn/opensource/os-cn-spring-cache/ http://swiftlet.net/archive ...

  3. Json::Value Use experience

    Json::Value yes sourceforge Open source project jsoncpp Data objects for , Used for processing json data   download 1. Print Json data Json::Value jv; Json::FastWriter ...

  4. 【 Multithreading 】-- Producer consumer model --synchronized edition

    Before realizing the producer consumer model , Let's take a look at threads first 5 States : Be created . function . frozen . Extinction . Blocking , Here's the picture : stay Jdk1.5 Before release , We implement the producer consumer model using synchronized + while loop ...

  5. Json Deserialization of .net Newtonsoft.Json

    There's a .json file . { "instances": [ { "name": "baidu", "url": &qu ...

  6. understand Load Average Do a stress test

    http://www.blogjava.net/cenwenchu/archive/2008/06/30/211712.html CPU Time slice In order to improve the efficiency of program execution , We have adopted multithreading mode in many applications ...

  7. 【NOIP simulation 】LCS And the number of schemes (DP)

    Description For a sequence

  8. liux Three swordsmen grep Regular matching

    001 Regular matching ( Most need to escape ) ‘^‘: Anchoring head '$' : Anchoring tail [0-9] A number [^0-9] Except the numbers, all ,^ Appear in the [] It means negation here [a-z] [A-Z] [a-Z] \s Match empty ...

  9. GUI Common dialog box 3

    % Progress bar %waitbar h=waitbar(,' example '); get(h); % Gets the sub object of the progress bar get(get(h,'Children')) ha=get(h,'Children'); % Get a seat ...

  10. ionic Hybrid application development

    windows Lower installation configuration npm install -g ionic npm install -g cordova ionic start myproject cd myproject ionic pl ...