Pagini recente » Cod sursa (job #1869971) | Cod sursa (job #2052650) | Cod sursa (job #2664524) | Cod sursa (job #1191024) | Cod sursa (job #3302752)
#include <bits/stdc++.h>
using namespace std;
namespace _2SAT
{
vector<int> v1[200005];
vector<int> v2[200005];
int vis[200005];
int ord[200005];
int cnt;
vector<int> comp[200005];
int what[200005];
#define v1 (v1+100002)
#define v2 (v2+100002)
#define vis (vis+100002)
void dfs1(int node)
{
vis[node] = 1;
for(auto &i : v1[node])
if(!vis[i])
dfs1(i);
ord[++cnt] = node;
}
void dfs2(int node, int color)
{
vis[node] = color;
for(auto &i : v2[node])
if(!vis[i])
dfs2(i, color);
}
vector<int> solve(int n, const vector<pair<int,int>> &edge)
{
for(const auto &i : edge)
{
v1[-i.first].push_back(i.second);
v1[-i.second].push_back(i.first);
v2[i.first].push_back(-i.second);
v2[i.second].push_back(-i.first);
}
for(int i=-n; i<=n; ++i)
if(i != 0 && !vis[i])
dfs1(i);
reverse(ord+1, ord+cnt+1);
int color = 0;
for(int i=1; i<=cnt; ++i)
vis[ord[i]] = 0;
for(int i=1; i<=cnt; ++i)
{
if(!vis[ord[i]])
dfs2(ord[i], ++color);
comp[vis[ord[i]]].push_back(ord[i]);
}
for(int i=1; i<=cnt; ++i)
if(vis[ord[i]] == vis[-ord[i]])
return vector<int>();
for(int i=1; i<=color; ++i)
{
for(auto &node : comp[i])
{
for(auto &oth : v2[node])
if(what[vis[oth]])
{
what[i] = 1;
break;
}
if(what[i]) break;
}
if(what[i]) continue;
for(auto &node : comp[i])
what[vis[-node]] = 1;
}
vector<int> ans(n+1);
for(int i=1; i<=n; ++i)
ans[i] = what[vis[i]];
return ans;
}
#undef v1
#undef v2
#undef vis
}
signed main()
{
ifstream fin ("2sat.in");
ofstream fout ("2sat.out");
ios::sync_with_stdio(false); fin.tie(0); fout.tie(0);
int n, m; fin>>n>>m;
vector<pair<int,int>> v;
while(m--)
{
int a, b; fin>>a>>b;
v.emplace_back(a, b);
}
const vector<int> &ans = _2SAT::solve(n, v);
if(ans.empty())
{
fout<<"-1";
return 0;
}
for(int i=1; i<=n; ++i)
fout<<ans[i]<<' ';
return 0;
}