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:
- A is invertible.
- Ax = b has exactly one solution for every
n × 1 matrix b.- Ax = b is consistent for every n × 1 matrix
b.- 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
传送门：【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 ;
}