uva 12167等価性証明
構想:テーマの意味によって、a,b,c,dなどの命題等価は導き(論理)の上で互いに相手を導き出すことができて、例えばa->b->c->d->aは明らかにこの時互いに導き出すことができて、これを図の上で1つの強い連通成分に置くことができて、
少なくともいくつかの関係を追加する必要があります.
では、まずお互いに導き出すことができる点を一つの点に縮めて、それからDAG図になります.加えて、入度0の点と出度0の点の個数を見て、原図が連通していることに注意します.
少なくともいくつかの関係を追加する必要があります.
では、まずお互いに導き出すことができる点を一つの点に縮めて、それからDAG図になります.加えて、入度0の点と出度0の点の個数を見て、原図が連通していることに注意します.
/*****************************************
Author :Crazy_AC(JamesQi)
Time :2015
File Name :
*****************************************/
// #pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <sstream>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <map>
#include <set>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <limits.h>
using namespace std;
#define MEM(a,b) memset(a,b,sizeof a)
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> ii;
const int inf = 1 << 30;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
inline int Readint(){
char c = getchar();
while(!isdigit(c)) c = getchar();
int x = 0;
while(isdigit(c)){
x = x * 10 + c - '0';
c = getchar();
}
return x;
}
const int maxn = 2e4 + 10;
int top,scc_cnt;
stack<int> s;
vector<int> G[maxn];
int low[maxn],pre[maxn],sccno[maxn],in[maxn],out[maxn];
void dfs(int u){
pre[u] = low[u] = ++top;
s.push(u);
for (int i = 0;i < G[u].size();++i){
int v = G[u][i];
if (!pre[v]){
dfs(v);
low[u] = min(low[u],low[v]);
}else if (!sccno[v]){
low[u] = min(low[u],pre[v]);
}
}
if (low[u] == pre[u]){
scc_cnt++;
for (;;){
int x = s.top();
sccno[x] = scc_cnt;
s.pop();
if (x == u) break;
}
}
}
void find_scc(int n){
top = scc_cnt = 0;
memset(sccno, 0,sizeof sccno);
memset(pre, 0,sizeof pre);
for (int i = 1;i <= n;i++)
if (!pre[i]) dfs(i);
}
int main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int T,n,m;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
for (int i = 1;i <= n;i++)
G[i].clear();
int a,b;
for (int i = 1;i <= m;i++){
scanf("%d%d",&a,&b);
G[a].push_back(b);//a->b;
}
find_scc(n);
memset(in, 0,sizeof in);
memset(out, 0,sizeof out);
for (int i = 1;i <= n;i++){
for (int j = 0;j < G[i].size();j++){
int v = G[i][j];
if (sccno[i] != sccno[v]){
in[sccno[v]]++;
out[sccno[i]]++;
}
}
}
a = 0,b = 0;
for (int i = 1;i <= scc_cnt;i++){
// printf("in:%d->%d
",i,in[i]);
// printf("out:%d->%d
",i,out[i]);
if (in[i] == 0) a++;
if (out[i] == 0) b++;
}
if (scc_cnt == 1) printf("%d
",0);
else printf("%d
",max(a,b));
}
return 0;
}