Proving Equivalences
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5168 Accepted Submission(s): 1807
Problem Description
Consider the following exercise, found in a generic linear algebra textbook.
Let A be an n × n matrix. Prove that the following statements 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 of implications. For instance, one can proceed by showing that (a) implies (b), that (b) implies (c), that (c) implies (d), and finally that (d) implies (a). These four implications show that the four statements are equivalent.
Another way would be to show that (a) is equivalent to (b) (by proving that (a) implies (b) and that (b) implies (a)), that (b) is equivalent to (c), and that (c) is equivalent to (d). However, this way requires proving six implications, which is clearly a lot more work than just proving four implications!
I have been given some similar tasks, and have already started proving some implications. Now I wonder, how many more implications do I have to prove? Can you help me determine this?
Input
On the first line one positive number: the number of testcases, at most 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 of implications 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
Source
题目大意：给出n个式子，m个推导关系，每个推导关系，表示公式a能够推出公式b，求还需要多少个式子，能够使得任意两个式子都能互相推导出来、
思路：
1、首先我们抽象化式子为节点，关系为边，将问题转化到图论上来，这里引入强连通的定义（有向图中）：如果a能有路径到达b，并且b能有路径到达a，那么称a和b是强连通的，我们想将所有点之间的关系都弄成强连通的，其实也就是在求，需要引入多少条边，能够使得图的强连通分量是1.
2、我们首先来观察一个强连通分量为1的图【注意看箭头方向】：
图1：
对于有向边，我们有入度和出度的定义。在上图中，每个节点的入度和出度都是1.也同时说明，对于一个强连通分量为1的图，出度和入度两种度中，一定两种度都没有0度的存在。我们不妨在观察一个强连通分量为1的图：
其1的出度：2，入度2。
其2的出度：1，入度1。
其3的出度：1，入度1.
我们再观察一个强连通分量不是1的图：
其1的出度为2，入度为0
其2的出度为0，入度为1
其3的出度为0，入度为1
那么我们要将这个图变成强连通分量为1的图，我们不妨这样考虑：既然强连通分量为1的图有这样的特点：如果一个图是强连通分量为1的图，对于每个节点来说，一定没有任何一个点的出度或者入度有0的情况。那么我们的任务也就明确了，对于所有节点度的处理，使得没有０度的存在。
那么我们对上图再进行分析，这里设出度为０的节点数为ａ，设入度为０的节点数为ｂ，其实我们如果找到了ａ和ｂ的值，搞定最大值，其实也就搞定了这个问题。
那么最终得到这样的结论：设定ｏｕｔｐｕｔ＝ｍａｘ（ａ，ｂ），假设ｏｕｔｐｕｔ＝ａ，那么就对出度为０的节点，一共连ａ条边，这些边都从出度为0的节点出发，到应该到的地方去。最终一定能使得图的出度和入度没有度为０的节点存在，同理，如果ｏｕｔｐｕｔ＝ｂ，也能够达成目标。
３、既然得到了结论，下一个动作就是做题啦~，因为图是会存在有向环的，所以我们使用Kosaraju算法来求出强连通分量，然后对所有属于一个强连通分量的点缩点看成一个点进行染色，然后统计入度出度，得到结果。
AC代码：
- #include<stdio.h>
- #include<string.h>
- #include<algorithm>
- using namespace std;
- int head[100000];
- int head2[100000];
- struct EdgeNode
- {
- int from;
- int to;
- int next;
- }e[300000],ee[300000],se[300000];
- int n,m,cont,cont2,sig;
- int in[1000000];
- int out[1000000];
- int vis[1000000];
- int num[1000000];
- int color[1000000];
- void add(int from,int to)
- {
- e[cont].from=from;
- e[cont].to=to;
- e[cont].next=head[from];
- head[from]=cont++;
- }
- void add2(int from,int to)
- {
- ee[cont2].from=from;
- ee[cont2].to=to;
- ee[cont2].next=head2[from];
- head2[from]=cont2++;
- }
- void init()
- {
- cont=0;
- cont2=0;
- memset(vis,0,sizeof(vis));
- memset(out,0,sizeof(out));
- memset(in,0,sizeof(in));
- memset(head,-1,sizeof(head));
- memset(head2,-1,sizeof(head2));
- memset(color,0,sizeof(color));
- memset(num,0,sizeof(num));
- }
- void Dfs(int u)
- {
- vis[u]=1;
- for(int i=head[u];i!=-1;i=e[i].next)
- {
- int v=e[i].to;
- if(vis[v]==0)
- {
- Dfs(v);
- }
- }
- num[sig++]=u;
- }
- void Dfs2(int u)
- {
- vis[u]=1;
- color[u]=sig;
- for(int i=head2[u];i!=-1;i=ee[i].next)
- {
- int v=ee[i].to;
- if(vis[v]==0)
- {
- Dfs2(v);
- }
- }
- }
- void Kosaraju()
- {
- sig=1;
- memset(vis,0,sizeof(vis));
- for(int i=1;i<=n;i++)
- {
- if(vis[i]==0)
- {
- Dfs(i);
- }
- }
- sig=0;
- memset(vis,0,sizeof(vis));
- for(int i=n;i>=1;i--)
- {
- if(vis[num[i]]==0)
- {
- sig++;
- Dfs2(num[i]);
- }
- }
- if(sig==1)
- {
- printf("0\n");
- return ;
- }
- for(int i=1;i<=n;i++)
- {
- for(int k=head[i];k!=-1;k=e[k].next)
- {
- int u=i,v=e[k].to;
- if(color[u]!=color[v])
- {
- out[color[u]]++;
- in[color[v]]++;
- }
- }
- }
- int ruu=0;
- int chu=0;
- for(int i=1;i<=sig;i++)
- {
- if(in[i]==0)ruu++;
- if(out[i]==0)chu++;
- }
- printf("%d\n",max(ruu,chu));
- }
- int main()
- {
- int t;
- scanf("%d",&t);
- while(t--)
- {
- init();
- scanf("%d%d",&n,&m);
- for(int i=0;i<m;i++)
- {
- int x,y;
- scanf("%d%d",&x,&y);
- add(x,y);
- add2(y,x);
- }
- Kosaraju();
- }
- }