﻿CSU 1802 小X的战斗力-Ocrosoft

# CSU 1802 小X的战斗力

Description

Input

Output

Sample Input

```2
5 5
4 3
4 2
3 2
1 2
2 5
3 3
1 2
2 3
3 1 ```

Sample Output

```-1
2
Wrong```

Hint

Solution

```#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define ms(a) memset(a,0,sizeof(a))
typedef long long LL;
const LL LINF = 1e17;
const int INF = INT_MAX / 2;
const int MAXN = 150 + 10;
const int MOD = 100000;
int gcd(int a, int b)
{
if (!b)return a;
return gcd(b, a%b);
}
using namespace std;
queue<int> q;
bool edge[MAXN][MAXN];
bool reach[MAXN][MAXN];
int in[MAXN];
int n, m;
bool topo()
{
for (int i = 1; i <= n; i++)
if (!in[i])q.push(i);
int cnt = 0;
while (!q.empty())
{
int t = q.front(); q.pop();
cnt++;
for (int i = 1; i <= n; i++)
{
if (edge[t][i])
{
in[i]--;
if (!in[i])q.push(i);
}
}
}
return cnt == n;
}
void floyd()
{
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
edge[i][j] |= edge[i][k] && edge[k][j];
}
int main()
{
int N;
cin >> N;
while (N--)
{
cin >> n >> m;
ms(edge); ms(in); ms(reach);
for (int i = 0; i < m; i++)
{
int u, v;
scanf("%d%d", &u, &v);
if (!edge[u][v])
{
edge[u][v] = 1;
in[v]++;
}
}
if (!topo())printf("Wrong\n");
else
{
floyd();
int loc = -1, ans = 0;
for (int i = 1; i <= n; i++)
{
int sum1 = 0, sum2 = 0;
for (int j = 1; j <= n; j++)
{
if (edge[i][j])sum1++;
if (edge[j][i])sum2++;
}
if (sum1 + sum2 + 1 == n)
{
ans++;
if (i == 1)loc = sum2 + 1;
}
}
printf("%d\n", loc);
printf("%d\n", ans);
}
}
return 0;
}```