给你一些命题 求最小还需要几次可以证明所有的命题都等价
一个强连通分量里面的题目都是等价的 只需缩点后 对于DAG图 入读为0和出度为0的点 两者之中最大值就是答案
如果只有1个强连通分量 那么无需证明了
#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
using namespace std;
const int maxn = 20010;
vector <int> G[maxn];
stack <int> s;
int pre[maxn];
int low[maxn];
int sccno[maxn];//每个点所在强联通分量的scc_cnt
int in[maxn];//每个强联通分量的入度
int out[maxn];//每个强联通分量的出度
int dfs_clock;
int scc_cnt;
int n, m;
void dfs(int u)
{
pre[u] = low[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);
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++;
while(1)
{
int x = s.top();
s.pop();
sccno[x] = scc_cnt;
if(x == u)
break;
}
}
}
void find_scc()
{
dfs_clock = scc_cnt = 0;
memset(sccno, 0, sizeof(sccno));
memset(pre, 0, sizeof(pre));
for(int i = 0; i < n; i++)
if(!pre[i])
dfs(i);
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++)
G[i].clear();
for(int i = 0; i < m; i++)
{
int u, v;
scanf("%d %d", &u, &v);
G[--u].push_back(--v);
}
find_scc();
for(int i = 1; i <= scc_cnt; i++)
in[i] = out[i] = 1;
for(int u = 0; u < n; u++)
{
for(int i = 0; i < G[u].size(); i++)
{
int v = G[u][i];
if(sccno[u] != sccno[v])
{
in[sccno[v]] = out[sccno[u]] = 0;
}
}
}
int a = 0, b = 0;
for(int i = 1; i <= scc_cnt; i++)
{
if(in[i])
a++;
if(out[i])
b++;
}
int ans = max(a, b);
if(scc_cnt == 1)
ans = 0;
printf("%d\n", ans);
}
return 0;
}