【ccf- csp201509-4】高速公路

 1 #include<iostream>
 2 using namespace std;
 3 void DFS(int**mat, int *mark,int *sp, int n, int p)
 4 {
 5     int i;
 6     //DFS每个顶点
 7     if(!mark[p])
 8     for(i=1;i<=n;i++)
 9         if (mat[p][i]&&i!=p)//<p,i>
10         {
11             mark[p] = 1;
12             sp[p] = 1;
13             DFS(mat,mark,sp, n, i);
14             mark[p] = 0;
15         }
16 }
17 int main()
18 {
19     int n, m,i,j; cin >> n >> m;
20     int**mat = new int*[n+1];
21     for (i = 0; i <= n; i++)
22         mat[i] = new int[n+1];
23     for (i = 0; i <= n; i++)
24         for (j = 0; j <= n; j++)
25             mat[i][j] = 0;
26     int a, b;
27     for (i = 0; i < m; i++)
28     {
29         cin >> a >> b;
30         mat[a][b] = 1;
31     }
32     int *mark = new int[n + 1];
33     int *sp = new int[n + 1];
34     int sum = 0,k;
35     for (i = 1; i <= n; i++)
36         mark[i] = 0;
37     for (i = 1; i < n; i++)
38     {
39         for (k = 1; k <= n; k++)
40             sp[k] = 0;
41         DFS(mat, mark, sp, n, i);
42         for (j = i + 1; j <= n; j++)
43         {
44             if (sp[j])//<i,j>
45             {
46                 for (k = 1; k <= n; k++)
47                     sp[k] = 0;
48                 DFS(mat, mark, sp, n, j);
49                 if (sp[i])//<j,i>
50                     sum++;
51             }
52         }
53     }
54     cout << sum << endl;
55     return 0;
56 }