Codeforces VK Cup 2012 Round 3 A. Variable, or There and Back Again(dfs)

题目链接：http://codeforces.com/problemset/problem/164/A

思路：用vector分别保留原图和发图，然后分别从val值为1的点正向遍历，va值为2的点反向遍历，如果某个点这两种方式都可以遍历到，则输出1，否则输出0.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define REP(i, a, b) for (int i = (a); i < (b); ++i)
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
using namespace std;

const int MAX_N = (100000 + 100);
int N, M, val[MAX_N], vis1[MAX_N], vis2[MAX_N];
int path[MAX_N];
vector<int > g1[MAX_N], g2[MAX_N];

void dfs(int u, int fa)
{
	vis1[u] = 1;
	REP(i, 0, (int)g1[u].size()) {
		int v = g1[u][i];
		if (!vis1[v] && v != fa && val[v] != 1) dfs(v, u);
	}
}

void rdfs(int u, int fa)
{
	vis2[u] = 1;
	if (val[u] == 1) return;
	REP(i, 0, (int)g2[u].size()) {
		int v = g2[u][i];
		if (!vis2[v] && v != fa) rdfs(v, u);
	}
}



int main()
{
	cin >> N >> M;
	FOR(i, 1, N) cin >> val[i];
	FOR(i, 1, M) {
		int u, v; cin >> u >> v;
		g1[u].push_back(v);
		g2[v].push_back(u);
	}
	FOR(i, 1, N)  {
		if (val[i] == 1) dfs(i, -1);
		else if (val[i] == 2) rdfs(i, -1);
	}
	FOR(i, 1, N) printf("%d
", (vis1[i] & vis2[i]));
	return 0;
}