Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

抄到ZJT的代码

Posted by jefflyy at 2014-11-22 12:31:48 on Problem 3905
#include<cstdio>
#include<cstring>
#include<vector>
#include<stack>
#define NOT(x) (x>n?x-n:x+n)
#define INF 0x7FFFFFFF
#define MAXN 2100
#define min(x,y) (x<y?x:y)
using namespace std;

vector<int> s[MAXN];
int nodeStack[MAXN];
bool visit[MAXN]={0},inStack[MAXN]={0};
int time=0;
int d[MAXN],low[MAXN];
int belong[MAXN];
int n,m;
int index=0;
int sum=1;

void dfs(int);

void addEdge(int x,int y)
{
	s[x].push_back(y);
}

int main()
{
	while(~scanf("%d%d",&n,&m))
	{
		for(int i=1;i<=n;i++)
		{
			s[i].clear();
			s[NOT(i)].clear();
		}
		time=0;
		index=0;
		memset(visit,0,sizeof visit);
		memset(inStack,0,sizeof inStack);
		memset(nodeStack,0,sizeof nodeStack);
		memset(d,0,sizeof d);
		memset(low,0,sizeof low);
		memset(belong,0,sizeof belong);
		sum=1;
		while(m--)
		{
			char s1='+',s2='+';
			int t1,t2;
			scanf("%d%d",&t1,&t2);
			if(t1<0)
			{
				t1=-t1;
				s1='-';
			}
			if(t2<0)
			{
				t2=-t2;
				s2='-';
			}
			if(s1=='+' && s2=='+')
			{
				addEdge(NOT(t1),t2);
				addEdge(NOT(t2),t1);
			}
			if(s1=='-' && s2=='-')
			{
				addEdge(t1,NOT(t2));
				addEdge(t2,NOT(t1));
			}
			if(s1=='+' && s2=='-')
			{
				addEdge(NOT(t1),NOT(t2));
				addEdge(t2,t1);
			}
			if(s1=='-' && s2=='+')
			{
				addEdge(t1,t2);
				addEdge(NOT(t2),NOT(t1));
			}
		}
		for(int i=1;i<=n;i++)
			if(!visit[i])
				dfs(i);
		for(int i=1;i<=n;i++)
			if(!visit[NOT(i)])
				dfs(NOT(i));
		bool check=1;
		for(int i=1;i<=n;i++)
			if(belong[i] && belong[i]==belong[NOT(i)])
			{
				printf("0\n");
				check=0;
				break;
			}
		if(check)
			printf("1\n");
	}
	return 0;
}

void dfs(int cur)
{
	visit[cur]=1;
	low[cur]=d[cur]=++time;
	nodeStack[++index]=cur;
	inStack[cur]=1;
	for(int i=0;i<s[cur].size();i++)
	{
		int v=s[cur].at(i);
		if(!visit[v])
		{
			dfs(v);
			low[cur]=min(low[cur],low[v]);
		}else if(inStack[v])
			low[cur]=min(low[cur],d[v]);
	}
	if(d[cur]==low[cur])
	{
		while(nodeStack[index]!=cur)
		{
			belong[nodeStack[index]]=sum;
			index--;
			inStack[nodeStack[index]]=0;
		}
		belong[cur]=sum;
		index--;
		inStack[cur]=0;
		sum++;
	}
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator