ZOJ4124 Median

题目链接：​​点击这里​​

n个数m组大小关系，求第i个数是否能作为第（n+1）2大的数。

拓扑判环，然后两次dfs

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

bool graph[110][110];
void floyd(int n)
{
  for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++)
        if (graph[i][k] && graph[k][j])
          graph[i][j] = true;
}


int main()
{
  int t;
  scanf("%d", &t);

  while (t--)
  {
    memset(graph, 0, sizeof(graph));
    int n, m;
    scanf("%d %d", &n, &m);

    while (m--)
    {
      int x, y;
      scanf("%d %d", &x, &y);
      graph[x][y] = true;
    }

    floyd(n);

    bool flg = true;
    for (int i = 1; i <= n; i++)
    {
      for (int j = 1; j <= n; j++)
      {
        if (graph[i][j] == graph[j][i] && graph[i][j] == 1)
        {
          flg = false;
        }
      }
    }
    int ans[110] = { 0 };
    if (flg)
      for (int i = 1; i <= n; i++)
      {
        int cnt1 = 0;
        int cnt2 = 0;
        for (int j = 1; j <= n; j++)
        {
          if (i == j)
            continue;
          if (graph[i][j])
            cnt1++;
          if (graph[j][i])
            cnt2++;
        }
        
        if (cnt1 <= n / 2 && cnt2 <= n / 2)
        {
          ans[i] = 1;
        }
      }
    for (int i = 1; i <= n; i++)
      printf("%d", ans[i]);
    printf("\n");
  }
;;;
  return 0;
}