2377.cpp

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

/* This Code is Submitted by wywcgs for Problem 2377 on 2006-09-28 at 20:55:34 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
const int MAX = 20002;
const int INF = 1<<30;
vector <int> g[MAX], gr[MAX];
stack <int> stk;
int n, dfn[MAX], low[MAX], num[MAX],c, id;
bool v[MAX];
inline void AddEdge(int a, int b)
{
	if (a<0) 
		a = (~a) + n;
	if (b<0)
		b = (~b) + n;
	g[a].push_back(b);
	gr[b].push_back(a);
}
void dfs(int v);
void dfs1(int u)
{
	v[u] = true;
	vector<int>::iterator it;
	for (it=g[u].begin(); it!=g[u].end(); ++it)
	{
		if (!v[*it])
			dfs1(*it);
	}
	stk.push(u);
}
void dfs2(int u)
{
	v[u] = true;
	num[u] = id;
	vector<int>::iterator it;
	for (it=gr[u].begin(); it!=gr[u].end(); ++it)
	{
		if (!v[*it])
			dfs2(*it);
	}
}
int main()
{
	int m;
	while (scanf("%d%d", &n, &m) == 2 && m+n)
	{
		int i, a, b, j;
		char str1[20], str2[20], line[1024];
		getchar();
		for (i=1; i<=m; i++)
		{
			gets(line);
			sscanf(line, "%s%d", str1, &a);
			for (j=0; line[j]!=0; j++)
			{
				if (line[j] == 'o' && line[j+1] == 'r')
				{
					j+=2;
					break;
				}
			}
			if (line[j]!=0)
			{
				sscanf(line+j, "%s%d", str2, &b);
				if (strcmp(str1, "Veto") == 0)
					a = ~a;
				if (strcmp(str2, "Veto") == 0)
					b = ~b;
				AddEdge(~a, b);
				AddEdge(~b, a);
			}
			else
			{
				if (strcmp(str1, "Approve") == 0)
					AddEdge(~a, a);
				else
					AddEdge(a, ~a);
			}
	
		}
		/*
		memset(v, false, sizeof(v));
		for (i=1; i<=2*n; i++)
		{
			if (!v[i])
				dfs1(i);
		}
		id = 1;
		memset(v,false, sizeof(v));
		while (!stk.empty())
		{
			int u = stk.top();
			stk.pop();
			if (!v[u])
			{
				dfs2(u);
				id++;
			}
		}*/
		memset(dfn, 0, sizeof(dfn));
		memset(num, 0, sizeof(num));
		c = id = 1;
		for (i=1; i<=2*n; i++)
		{
			if (dfn[i] == 0)
			{
				dfs(i);
			}
		}
		
		for (i=1; i<=n; i++)
			if (num[i] == num[i+n])
				break;
		if (i<=n)
			printf("No, keep going.\n");
		else
			printf("Yes, we are done.\n");
		for (i=1; i<=2*n; i++)
		{
			g[i].clear();
			gr[i].clear();
		}
	}
	return 0;
}


void dfs(int v)
{
	int h = dfn[v] = low[v] = c++;
	vector<int>::iterator it;
	stk.push(v);
	for (it=g[v].begin(); it!=g[v].end(); ++it)
	{
		int w = *it;
		if (dfn[w]==0)
		{
			dfs(w);
			
		}
		h = min(low[w], h);
	}
	if (h == low[v])
	{
		while (true)
		{
			int w = stk.top();
			stk.pop();
			num[w] = id;
			low[w] = INF;
			if (w == v)
			{
				id++;
				break;
			}
		}
	} else low[v] = h;
}