1917.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1917 on 2006-08-09 at 12:35:21 */ 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
const int N = 16384;
 
class Graph {
private:
	vector<int> n[N], sc[N], dag[N];
	bool vst[N];
	int pn, v, scn[N], dfn[N], low[N], cnt, scnt;
	int stack[N], top;
	int no(int b) const { return (b&1) ? (b>>1) : (b>>1)+pn; }
	int yes(int b) const { return (b&1) ? (b>>1)+pn : (b>>1); }
	void scR();
	void dfs(int);
	void color(int);
public:
	bool build();
	void establish();
};
void Graph::dfs(int u) {
	int i, k, h = dfn[u] = low[u] = cnt++;
	stack[top++] = u;
	for(i = n[u].size()-1; i >= 0; i--) {
		int p = n[u][i];
		if(dfn[p] == -1) dfs(p);
		h <?= low[p];
	}
	if(h < dfn[u]) { low[u] = h; return; }
	do {
		k = stack[--top];
		sc[scnt].push_back(k); scn[k] = scnt; low[k] = N;
	} while(k != u);
	scnt++;
}
void Graph::scR() {
	cnt = scnt = top = 0;
	memset(dfn, -1, sizeof(dfn));
	int i;
	for(i = 0; i < v; i++) sc[i].clear();
	for(i = 0; i < v; i++)
		if(dfn[i] == -1) dfs(i);
}
void Graph::color(int u) {
	if(!vst[u]) return;
	vst[u] = false;
	int i;
	for(i = dag[u].size()-1; i >= 0; i--) color(dag[u][i]);
}
bool Graph::build() {
	int i, m;
	if(scanf("%d %d", &pn, &m) == EOF) return false;
	v = pn<<1;
	for(i = 0; i < v; i++) n[i].clear();
	for(i = 0; i < m; i++) {
		int a, b; scanf("%d %d", &a, &b); a--; b--;
		n[yes(a)].push_back(no(b)); n[yes(b)].push_back(no(a));
	}
	return true;
}
void Graph::establish() {
	scR(); int i, j, id[N];
	for(i = 0; i < pn; i++)
		if(scn[i] == scn[i+pn]) { printf("NIE\n"); return; }
	for(i = 0; i < scnt; i++) dag[i].clear();
	memset(id, 0, sizeof(id)); memset(vst, true, sizeof(vst));
	for(i = 0; i < v; i++)
		for(j = n[i].size()-1; j >= 0; j--) {
			int u = n[i][j];
			if(scn[i] == scn[u]) continue;
			id[scn[i]]++; dag[scn[u]].push_back(scn[i]);
		}
	top = 0;
	for(i = 0; i < scnt; i++)
		if(id[i] == 0) stack[top++] = i;
	while(top > 0) {
		int u = stack[--top];
		if(!vst[u]) continue;
		vst[u] = true;
		for(i = sc[u].size()-1; i >= 0; i--) color(scn[(sc[u][i]+pn)%v]);
		for(i = dag[u].size()-1; i >= 0; i--)
			if(--id[dag[u][i]] == 0) stack[top++] = dag[u][i];
	}
	for(i = 0; i < pn; i++)
		printf("%d\n", vst[scn[i]] ? 2*i+1 : 2*i+2);
}
 
Graph g;
 
int main()
{
	while(g.build()) g.establish();
	
	return 0;
}