【UVALive】4287 Proving Equivalences 強連通分量

4287. Proving Equivalences

Consider the following exercise, found in a generic linear algebratextbook.

Let A be an n × n matrix. Prove that the followingstatements are equivalent:

1. A is invertible.
2. Ax = b has exactly one solution for every n × 1 matrix b.
3. Ax = b is consistent for every n × 1 matrix b.
4. Ax = 0 has only the trivial solution x = 0.

The typical way to solve such an exercise is to show a series ofimplications. For instance, one can proceed by showing that (a)implies (b), that (b) implies (c), that (c) implies (d), and finallythat (d) implies (a). These four implications show that the fourstatements are equivalent.

Another way would be to show that (a) is equivalent to (b) (by provingthat (a) implies (b) and that (b) implies (a)), that (b) is equivalentto (c), and that (c) is equivalent to (d). However, this way requiresproving six implications, which is clearly a lot more work than justproving four implications!

I have been given some similar tasks, and have already started provingsome implications. Now I wonder, how many more implications do I haveto prove? Can you help me determine this?

Input

On the first line one positive number: the number of testcases, atmost 100. After that per testcase:

• One line containing two integers n (1 ≤ n ≤ 20000) and m(0 ≤ m ≤ 50000): the number of statements and the number ofimplications that have already been proved.
• m lines with two integers s1 and s2 (1 ≤ s1, s2 ≤ n and s1 ≠ s2) each, indicating that it has been proved that statement s1 implies statement s2.

Output

Per testcase:

• One line with the minimum number of additional implications that need to be proved in order to prove that all statements are equivalent.

Sample Input

2
4 0
3 2
1 2
1 3
      

Sample Output

4
2
      

The 2008 ACM Northwestern European Programming Contest

傳送門：【UVALive】4287 Proving Equivalences

題目大意：

在數學中，我們常常需要完成若幹命題的等價性證明。比如有4個命題a，b，c，d，我們證明a<->b，b<->c，c<->d。注意每次證明都是雙向的，是以一共完成了6次推導。另一種方法是證明a->b，b->c，c->d，d->a，隻需四次。

現在你的任務是證明n個命題全部等價，且你的朋友已經為你做出了m次推導（已知推導的内容），你至少還需要做幾次推導才能完成整個證明？

題目分析：

把命題看作結點，推導看作有向邊，則本題就是給出n個結點m條邊的有向圖，要求填加盡量少的邊，使得新圖強連通。

首先找出強連通分量，然後把每個強連通分量縮成一個點，得到一個DAG。接下來，設有a個結點（這裡的每個結點對應原圖的強連通分量）的入度為0，b個結點的出度為0，則答案就是max{a , b}。

為什麼呢？因為如果新圖強連通，則新圖上的點一定沒有入度或出度為0的點，那麼最少的添加邊的數量就是其中的最大值。

代碼如下：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std ;

#define clear( A , X ) memset ( A , X , sizeof A )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define FF( i , a , b ) for ( int i = a ; i <= b ; ++ i )

const int maxN = 20005 ;
const int maxM = 50005 ;
const int maxS = 20005 ;
const int maxE = 1000005 ;

struct Edge {
	int v , n ;
	Edge () {}
	Edge ( int var , int next ) : v(var) , n(next) {}
} ;

struct SCC {
	Edge edge[maxE] ;
	int adj[maxN] , cntE ;
	int scc[maxN] , ins[maxN] , Dfn[maxN] , Low[maxN] , scc_cnt ;
	int S[maxS] , top , dfs_clock ;
	int in[maxN] , ou[maxN] ;
	
	void addedge ( int u , int v ) {
		edge[cntE] = Edge ( v , adj[u] ) ;
		adj[u] = cntE ++ ;
	}
	
	void Tarjan ( int u ) {
		S[top ++] = u ;
		ins[u] = 1 ;
		Dfn[u] = Low[u] = ++ dfs_clock ;
		for ( int i = adj[u] ; ~i ; i = edge[i].n ) {
			int v = edge[i].v ;
			if ( !Dfn[v] ) {
				Tarjan ( v ) ;
				Low[u] = min ( Low[u] , Low[v] ) ;
			}
			else if ( ins[v] ) {
				Low[u] = min ( Low[u] , Dfn[v] ) ;
			}
		}
		if ( Low[u] == Dfn[u] ) {
			++ scc_cnt ;
			while ( 1 ) {
				int v = S[-- top] ;
				ins[v] = 0 ;
				scc[v] = scc_cnt ;
				if ( v == u ) break ;
			}
		}
	}
	
	void Init () {
		top = 0 ;
		cntE = 0 ;
		scc_cnt = 0 ;
		dfs_clock = 0 ;
		clear ( Dfn , 0 ) ;
		clear ( ins , 0 ) ;
		clear ( adj , -1 ) ;
	}
	
	void Find_SCC ( int n ) {
		FF ( i , 1 , n )
			if ( !Dfn[i] )
				Tarjan ( i ) ;
	}
	
	void Solve ( int n ) {
		if ( scc_cnt == 1 ) {
			printf ( "0\n" ) ;
			return ;
		}
		clear ( in , 0 ) ;
		clear ( ou , 0 ) ;
		FF ( u , 1 , n )
			for ( int i = adj[u] ; ~i ; i = edge[i].n ) {
				int v = edge[i].v ;
				if ( scc[u] != scc[v] ) {
					ou[scc[u]] = 1 ;
					in[scc[v]] = 1 ;
				}
			}
		int No_In = 0 , No_Out = 0 ;
		FF ( i , 1 , scc_cnt ) {
			if ( !in[i] ) ++ No_In ;
			if ( !ou[i] ) ++ No_Out ;
		}
		printf ( "%d\n" , max ( No_In , No_Out ) ) ;
	}
} ;

SCC scc ;

void work () {
	int n , m , u , v ;
	scc.Init () ;
	scanf ( "%d%d" , &n , &m ) ;
	REP ( i , m ) {
		scanf ( "%d%d" , &u , &v ) ;
		scc.addedge ( u , v ) ;
	}
	scc.Find_SCC ( n ) ;
	scc.Solve ( n ) ;
}

int main () {
	int T ;
	scanf ( "%d" , &T ) ;
	while ( T -- )
		work () ;
	return 0 ;
}