Pagini recente » Borderou de evaluare (job #2764527) | Cod sursa (job #2798767)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
std::ifstream in("2sat.in");
std::ofstream out("2sat.out");
const int N=100000;
std::vector<int> v[2*N+1];
std::vector<int> t[2*N+1];
int ctc[2*N+1];
int n, m;
int opus(int x)
{
if(x<=N) return x+N;
return x-N;
}
bool srt[2*N+1];
std::stack<int> q;
void sort_top(int i)
{
srt[i]=true;
for(int copil : v[i])
{
if(!srt[copil])
{
sort_top(copil);
}
}
q.push(i);
}
void Kosaraju(int i, int nr)
{
ctc[i]=nr;
for(int copil : t[i])
{
if(!ctc[copil])
{
Kosaraju(copil, nr);
}
}
}
int nr=0;
int main()
{
int x, y;
in>>n>>m;
for(int i=1; i<=m; i++)
{
in>>x>>y;
if(x<0)
{
x=(-x)+N;
}
if(y<0)
{
y=(-y)+N;
}
v[opus(x)].push_back(y);
v[opus(y)].push_back(x);
t[y].push_back(opus(x));
t[x].push_back(opus(y));
}
/// sortare top
for(int i=1; i<=2*N; i++)
{
if(!srt[i] && (v[i].size()>0 || t[i].size()>0))
{
sort_top(i);
}
}
/// Kosaraju
while(!q.empty())
{
if(ctc[q.top()]==0)
{
nr++;
Kosaraju(q.top(), nr);
}
q.pop();
}
// for(int i=1; i<=n; i++)
// {
// if(ctc[i]==ctc[i+N])
// {
// out<<-1;
// return 0;
// }
// }
for(int i=1; i<=n; i++)
{
out<<(ctc[i]>ctc[opus(i)])<<" ";
}
}