acmicpc.net 11277,11280,11281(2-SAT)

https://www.acmicpc.net/problem/11277

https://www.acmicpc.net/problem/11280

#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
#include <utility>
#include <algorithm>
#include <iostream>
using namespace std;
typedef pair<int, int> P;
const int MAX = 100001;
 
int N, M, cnt, dfsn[MAX], SN, sn[MAX];
vector<int> adj[MAX];
bool finished[MAX]; 
stack<int> S;
vector<vector<int>> SCC;
 
inline int oppo(int n){ return n%2 ? n-1 : n+1; }
 
int DFS(int curr){
    dfsn[curr] = ++cnt; 
    S.push(curr); 
   
    int result = dfsn[curr];
    for(int next: adj[curr]){
        if(dfsn[next] == 0) 
            result = min(result, DFS(next));
        else if(!finished[next]) 
            result = min(result, dfsn[next]);
    }
   
    if(result == dfsn[curr])
    {
        vector<int> currSCC;
        while(1)
        {
            int t = S.top();
            S.pop();
            currSCC.push_back(t);
            finished[t] = true;
            sn[t] = SN;
            if(t == curr) break;
        }
        sort(currSCC.begin(), currSCC.end());
        SCC.push_back(currSCC);
        SN++;
    }
    return result;
}
 
int main(){
    cin>>N>>M;
    for(int i=0; i<M; i++){
        int A, B;
        cin>>A>>B;

		if(A<0) A=-(A+1)*2;
		else A=A*2-1;
		if(B<0) B=-(B+1)*2;
		else B=B*2-1;
		//cout<<"a = "<<A<<", b = "<<B<<endl; //-1 = 0, 1 = 1, -2 = 2, 2 = 3
        adj[oppo(A)].push_back(B); 
        adj[oppo(B)].push_back(A); 
    }
 
    for(int i=0; i<N*2; i++)
        if(dfsn[i] == 0) 
			DFS(i);
 
    for(int i=0; i<N; i++){
        if(sn[i*2] == sn[i*2+1]){
            cout<<"0\n";
            return 0;
        }
    }
    cout<<"1\n";
}

https://www.acmicpc.net/problem/11281

#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
#include <utility>
#include <algorithm>
#include <iostream>
using namespace std;
typedef pair<int, int> P;
const int MAX = 100001;
  
int N, M, cnt, dfsn[MAX], SN, sn[MAX];
vector<int> adj[MAX];
bool finished[MAX]; 
stack<int> S;
vector<vector<int>> SCC;
  
inline int oppo(int n){ return n%2 ? n-1 : n+1; }
  
int DFS(int curr){
    dfsn[curr] = ++cnt; 
    S.push(curr); 
    
    int result = dfsn[curr];
    for(int next: adj[curr]){
        if(dfsn[next] == 0) 
            result = min(result, DFS(next));
        else if(!finished[next]) 
            result = min(result, dfsn[next]);
    }
    
    if(result == dfsn[curr])
    {
        vector<int> currSCC;
        while(1)
        {
            int t = S.top();
            S.pop();
            currSCC.push_back(t);
            finished[t] = true;
            sn[t] = SN;
            if(t == curr) break;
        }
        sort(currSCC.begin(), currSCC.end());
        SCC.push_back(currSCC);
        SN++;
    }
    return result;
}
  
int main(){
	int result[MAX]; 
    cin>>N>>M;
    for(int i=0; i<M; i++){
        int A, B;
        cin>>A>>B;
 
        if(A<0) A=-(A+1)*2;
        else A=A*2-1;
        if(B<0) B=-(B+1)*2;
        else B=B*2-1;
        //cout<<"a = "<<A<<", b = "<<B<<endl; //-1 = 0, 1 = 1, -2 = 2, 2 = 3
        adj[oppo(A)].push_back(B); 
        adj[oppo(B)].push_back(A); 
    }
  
    for(int i=0; i<N*2; i++)
        if(dfsn[i] == 0) 
            DFS(i);
  
    for(int i=0; i<N; i++){
        if(sn[i*2] == sn[i*2+1]){
            cout<<"0\n";
            return 0;
        }
    }
    cout<<"1\n";
	
	for(int i=0;i<MAX;i++)
		result[i]=-1;
    P p[MAX*2];
    for(int i=0; i<N*2; i++)
        p[i] = P(sn[i], i);
    sort(p, p+N*2);
 
    for(int i=N*2-1; i>=0; i--)
	{
        int var = p[i].second;
        if(result[var/2] == -1) 
			result[var/2] = !(var%2);
    }
    for(int i=0; i<N; i++)
        cout<<result[i]<<" ";
}