UVALive 4262——Trip Planning——————【Tarjan 求强连通分量个数】-白红宇

UVALive 4262——Trip Planning——————【Tarjan 求强连通分量个数】

阅读量：5094 次

发布时间：2019-06-13

本文共 5342 字，大约阅读时间需要 17 分钟。

Road Networks

Time Limit:3000MS Memory Limit:0KB 64bit IO Format:%lld & %llu

Submit

Description

There is a road network comprised by M<tex2html_verbatim_mark> roads and N<tex2html_verbatim_mark> cities. For convenience, we use {1, 2,..., N}<tex2html_verbatim_mark> to denote the N<tex2html_verbatim_mark> cities. Each road between two cities i<tex2html_verbatim_mark> and j<tex2html_verbatim_mark> , where 1 $\le$ i<tex2html_verbatim_mark> , j $\le$ N<tex2html_verbatim_mark> and i $\neq$ j<tex2html_verbatim_mark> , has two types: One type is bidirectional, which allows a citizen to drive a car from i<tex2html_verbatim_mark> to j<tex2html_verbatim_mark> (denoted by i $\leadsto$ j<tex2html_verbatim_mark> ) and from j<tex2html_verbatim_mark> to i<tex2html_verbatim_mark> (denoted by j $\leadsto$ i<tex2html_verbatim_mark> ). The other type is unidirectional, which allows a citizen to drive a car following exactly one direction, either from i<tex2html_verbatim_mark> to j<tex2html_verbatim_mark> or from j<tex2html_verbatim_mark> to i<tex2html_verbatim_mark> .

We say that City j<tex2html_verbatim_mark> is reachable from City i<tex2html_verbatim_mark> if one can drive a car from i<tex2html_verbatim_mark> to j<tex2html_verbatim_mark> , visiting a sequence of cities c₁, c₂,..., c_k<tex2html_verbatim_mark> for k $\ge$ 0<tex2html_verbatim_mark> , such thati $\leadsto$ c₁ $\leadsto$ c₂ $\leadsto$ ... $\leadsto$ c_k $\leadsto$ j<tex2html_verbatim_mark> . (Every city is always reachable from itself.) A region is a maximal set of cities so that the following mutually reachable property holds: for two arbitrary cities i<tex2html_verbatim_mark> and j<tex2html_verbatim_mark> , i<tex2html_verbatim_mark> is reachable from j<tex2html_verbatim_mark> and j<tex2html_verbatim_mark> is also reachable from i<tex2html_verbatim_mark> . The adjective ``maximal" means that if we include any other city in the given region, the mutually reachable property cannot be retained. Given a road network, your task is to write a computer program to compute the number of regions in the road network.

Technical Specification

We use {1, 2,..., N}<tex2html_verbatim_mark> to denote the N<tex2html_verbatim_mark> cities.

M $\le$ 2000<tex2html_verbatim_mark> is a non-negative integer

N $\le$ 1000<tex2html_verbatim_mark> is a positive integer.

If a road between i<tex2html_verbatim_mark> and j<tex2html_verbatim_mark> is bidirectional, then we use two order pairs (i, j)<tex2html_verbatim_mark> and (j, i)<tex2html_verbatim_mark> to represent it. Otherwise, if a road between i<tex2html_verbatim_mark>and j<tex2html_verbatim_mark> is unidirectional from i<tex2html_verbatim_mark> to j<tex2html_verbatim_mark> (respectively, j<tex2html_verbatim_mark> to i<tex2html_verbatim_mark> ), we use ( i<tex2html_verbatim_mark> , j<tex2html_verbatim_mark> ) (respectively, ( j<tex2html_verbatim_mark> , i<tex2html_verbatim_mark> )) to represent it.

Input

The input consists of a number of test cases. The first line of the input file contains an integer indicating the number of test cases to follow. Each test case consists of a road network, which has the following format: the first line of each test case contains two numbers, N<tex2html_verbatim_mark>and M<tex2html_verbatim_mark> , separated by a single space. The next M<tex2html_verbatim_mark> lines contain the description of M<tex2html_verbatim_mark> roads such that one line contains two cities representing an order pair (i, j)<tex2html_verbatim_mark> . Each line is represented by two positive numbers separated by a single space; the first number representing the former element in the order pair and the second number representing the latter element in the order pair. A ` 0' at the (M+ 2)<tex2html_verbatim_mark> -th line of each test case (except for the last test case) indicates the end of this test case.

The next test case starts after the previous ending symbol `0'. Finally, a `-1' signals the end of the whole inputs.

Output

The output contains one line for each test case. Each line contains an integer, which is the number of the regions in the given road network.

Sample Input

2 3 21 21 30 3 31 22 33 1-1

Sample Output

3 1 题目大意：给你n个点，m条有向边。问你这个图中的scc个数。 解题思路：求强连通分量的模板题，Tarjan算法水过。

/*    Tarjan     求强连通分量个数*/#include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;const int maxn = 1e5+200;vector
              
               G[maxn];int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;stack
               
                S;void dfs(int u){ pre[u] = lowlink[u] = ++dfs_clock; S.push(u); for(int i = 0;i < G[u].size(); i++){ int v = G[u][i]; if(!pre[v]){ dfs(v); lowlink[u] = min(lowlink[u], lowlink[v]); }else if(!sccno[v]){ lowlink[u] = min(lowlink[u], pre[v]); } } if(lowlink[u] == pre[u]){ scc_cnt++; for(;;){ int x = S.top(); S.pop(); sccno[x] = scc_cnt; if(x == u) break; } }}void find_scc(int n){ dfs_clock = scc_cnt = 0; while(!S.empty()) S.pop(); memset(sccno , 0, sizeof(sccno)); memset(pre, 0, sizeof(pre)); for(int i = 1; i <= n; i++){ if(!pre[i]) dfs(i); }}int main(){ int T,n,m; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); int a,b; for(int i = 0; i < m; i++){ scanf("%d%d",&a,&b); G[a].push_back(b); } scanf("%d",&a); find_scc(n); printf("%d\n",scc_cnt); for(int i = 0; i <= n; i++){ G[i].clear(); } } return 0;}

转载于:https://www.cnblogs.com/chengsheng/p/4887059.html

你可能感兴趣的文章