描述

Vani和cl2在一片树林里捉迷藏。这片树林里有N座房子,M条有向道路,组成了一张有向无环图。N≤200,M≤30000。
树林里的树非常茂密,足以遮挡视线,但是沿着道路望去,却是视野开阔。如果从房子A沿着路走下去能够到达B,那么在A和B里的人是能够相互望见的。
现在cl2要在这N座房子里选择K座作为藏身点,同时Vani也专挑cl2作为藏身点的房子进去寻找,为了避免被Vani看见,cl2要求这K个藏身点的任意两个之间都没有路径相连。
为了让Vani更难找到自己,cl2想知道最多能选出多少个藏身点。

输入格式

输入数据的第一行是两个整数N和M。接下来M行,每行两个整数 x,y,表示一条从 x 到 y 的有向道路。

输出格式

输出一个整数K,表示最多能选取的藏身点个数。

在第二行输出 K 个空格分开的整数,表示选择的藏身点编号。如果有多个方案,输出任意一个即可。编号的输出顺序任意。

样例输入

7 5
1 2
3 2
2 4
4 5
4 6

样例输出

3
1 3 7

数据范围与约定

  • 对于20% 的数据,N≤10,M<=20。
    对于60% 的数据, N≤100,M<=1000。
    对于100% 的数据,N≤200,M<=30000,1<=x,y<=N。

本题校验器(SPJ)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
//一些定义
const int ACCEPT = 0;
const int WRONG_ANSWER = 1;
//fstd 标准输出 fout 选手输出 fin 标准输入
FILE *fstd,*fout,*fin;
int n, m, ans, val;
bool v[210], f[210];
vector<int> ver[210];

bool dfs(int x) {
	f[x] = 1;
	if (v[x]) return true;
	for (int i = 0; i < ver[x].size(); i++) {
		int y = ver[x][i];
		if (f[y]) continue;
		if (dfs(y)) return true;
	}
	return false;
}

//执行比较操作。
bool DoCompare(){
	fscanf(fin, "%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
    	int x, y;
		fscanf(fin, "%d%d", &x, &y);
		ver[x].push_back(y);
	}
    fscanf(fstd, "%d", &ans);
    fscanf(fout, "%d", &val);
    // 答案不对 
    if (val != ans) return false;
    for (int i = 1; i <= ans; i++) {
    	int x; fscanf(fout, "%d", &x);
    	// 输出的藏身点不合法或有重复 
    	if (x < 1 || x > n || v[x]) return false;
    	v[x] = 1;
    }
    for (int i = 1; i <= n; i++) {
    	if (!v[i]) continue;
		memset(f, 0, sizeof(f));
		v[i] = 0;
		// 能看到别的点 
    	if (dfs(i)) return false;
    	v[i] = 1;
    }
    return true;
}

int main(int argc, char* argv[])
{
    if(argc!=4){
        printf("参数不足 %d",argc);
        return -1;
    }

    //打开文件
    if(NULL==(fstd=fopen(argv[1],"r"))){
        return -1;
    }
    if(NULL==(fout=fopen(argv[2],"r"))){
        return -1;
    }
    if(NULL==(fin=fopen(argv[3],"r"))){
        return -1;
    }

    if(DoCompare()){
        return ACCEPT;
    }else{
        return WRONG_ANSWER;
    }
}