Cod sursa(job #2591429)

Utilizator SchnitzelMannPavaloiu Gabriel SchnitzelMann Data 30 martie 2020 15:29:31
Problema 2SAT Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <bits/stdc++.h>
#define N 200002
using namespace std;
ifstream in("2sat.in");
ofstream out("2sat.out");
vector<int> v[N];
stack<int> s;
int a[N],n;
int co(int i)
{
	return (i+n)%(2*n);
}
void dfs(int i)
{
	if(a[i])
		return;
	a[i]=1;
	for(auto it:v[i])
		dfs(it);
	s.push(i);
}
int main()
{
	int m,i,j;
	in>>n>>m;
	while(m--)
	{
		in>>i>>j;
		i=(i>0)*n+abs(i)-1;
		j=(j>0)*n+abs(j)-1;
		v[co(i)].push_back(j);
		v[co(j)].push_back(i);
	}
	for(i=0;i<2*n;i++)
		dfs(i);
	memset(a,0,sizeof(a));
	for(;!s.empty();s.pop())
		if(!a[s.top()]&&!a[co(s.top())])
			a[co(s.top())]=1;
	for(i=0;i<2*n;i++)
		if(a[i])
			for(auto it:v[i])
				if(!a[it])
				{
					out<<-1;
					return 0;
				}
	for(i=n;i<2*n;i++)
		out<<a[i]<<" ";
	return 0;
}