Semiconnected--強連通縮点

1451: Semiconnected

時間制限:1 Sec
メモリ制限:32 MB
提出:79
解決:20

タイトルの説明

For a directed graph G = (V, E), if for all pairs of nodes u,v, u can always reach v or v can always reach u , then we call this a Semiconnected graph. Now you are given a directed graph, you should tell us whether it is a Semiconnected graph. If it is, output “yes”, or else“no”.

入力

There are several test cases, for each test case, there are two integers in the first line, n and m n(n<=10000) ,m(m<=50000) , means that there are n nodes and m edges in this graph. The nodes are numbered from 1 to n. Then m lines each with two integers u and v means there is an edge from u to v.

しゅつりょく

For each test case, output “yes” if it is a Semiconnected graph, or else “no” instead.

サンプル入力

4 3

1 2

2 3

3 4

4 3

1 2

2 3

4 3

サンプル出力

yes

no

标题:有向図をあげます.もし図の中の任意の2つの点u,vから.いずれもuからvへの経路、またはvからuへの経路がある場合、この図は半連通であり、yesが出力され、noが出力される
構想:この図が以上の状況に合致する場合、
1:入力が0の点が1つ以上で、一致しません.
2:この図を縮点した後、半連通図であれば、現在の図は一直線で、新図中の入度を統計し、出度が0の点はいずれも1つだけでよいか.
コードは次のとおりです.

#include "stdio.h"  //      ，        0，   0         
#include "string.h"
#include "vector"
#include "stack"
using namespace std;

#define N 10005
#define M 50005

struct node
{
    int x,y;
    int next;
}edge[M];
int idx,head[N];
void Init(){ idx=0; memset(head,-1,sizeof(head)); }
void Add(int x,int y)
{
    edge[idx].x=x; edge[idx].y=y;
    edge[idx].next=head[x]; head[x]=idx++;
}

int n;
int dfs_clock;
bool mark[N];
int scc_cnt;
int belong[N];
stack q;
int num[N];
int low[N],dfn[N];
int MIN(int a,int b) { return a1) { printf("no
"); continue; }
        Solve(id);
    }
    return 0;
}