1858.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1858 on 2006-08-06 at 11:30:08 */ 
#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 v, m, scn[N], dfn[N], low[N], cnt, scnt;
	int stack[N], top;
	void scR();
	void dfs(int);
	void color(int);
public:
	bool build();
	void visitCity();
};
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 = min(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, pn;
	if(scanf("%d %d", &pn, &m) == EOF) return false;
	v = m*2;
	for(i = 0; i < v; i++) n[i].clear();
	for(i = 0; i < pn; i++) {
		int a, b; scanf("%d %d", &a, &b);
		if(a < 0) a = -a+m;
		if(b < 0) b = -b+m;
		a--; b--;
		n[(a+m)%v].push_back(b); n[(b+m)%v].push_back(a);
	}
	return true;
}
void Graph::visitCity() {
	scR(); int i, j, id[N];
	for(i = 0; i < m; i++)
		if(scn[i] == scn[i+m]) { printf("NO\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]+m)%v]);
		for(i = dag[u].size()-1; i >= 0; i--)
			if(--id[dag[u][i]] == 0) stack[top++] = dag[u][i];
	}
	int vn = 0, kn = 0;
	for(i = 0; i < m; i++)
		if(vst[scn[i]]) vn++;
	printf("%d\n", vn);
	for(i = 0; i < m; i++)
		if(vst[scn[i]]) { kn++; printf("%d%c", i+1, kn == vn ? '\n' : ' '); }
}

Graph g;

int main()
{
	while(g.build()) g.visitCity();
	
	return 0;
}