学步园

关键是要明确在最坏情况下需要比较n * (n - 1) / 2次。

之后的事情就简单了，把已得到的两两关系算出来，然后看还差多少。O(nm)。

 

 1 #include <cstdio>
 2 #include <vector>
 3 using namespace std;
 4 
 5 const int N = 1000;
 6 
 7 int n, m;
 8 bool mk[N + 1];
 9 vector<int> adj[N + 1];
10 
11 int dfs(int u)
12 {
13     mk[u] = true;
14     int sum = 1;
15     for (vector<int>::iterator it = adj[u].begin(); it != adj[u].end(); ++it)
16     {
17         if (!mk[*it]) sum += dfs(*it);
18     }
19     return sum;
20 }
21 
22 int main()
23 {
24     scanf("%d%d", &n, &m);
25     for (int i = 0; i < m; i++)
26     {
27         int a, b;
28         scanf("%d%d", &a, &b);
29         adj[a].push_back(b);
30     }
31     
32     int cmp = 0;
33     for (int i = 1; i <= n; i++)
34     {
35         fill(mk + 1, mk + n + 1, false);
36         cmp += dfs(i) - 1;
37     }
38     printf("%d\n", n * (n - 1) / 2 - cmp);
39     
40     return 0;
41 }
42