acmicpc.net 2207(2-SAT), 3747(2-SAT), 3648(2-SAT)

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

#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<N; 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<<"OTL\n";
            return 0;
        }
    }
    cout<<"^_^\n";
}

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

위 코드에서 main부분만 바꿔준다.

int main(){
	while(1)
	{
		cnt = 0; SN = 0;
		for(int i=0;i<MAX;i++)
			adj[i].clear();
		memset(dfsn,0,sizeof(dfsn));
		memset(sn,0,sizeof(dfsn));
		memset(finished,0,sizeof(finished));

		if(scanf("%d",&N)==-1)//cin>>N>>M;
			break;
		scanf("%d",&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);
   
		bool flag = true;
		for(int i=0; i<N; i++){
			if(sn[i*2] == sn[i*2+1]){
				cout<<"0\n";
				flag = false;
				break;
			}
		}
		if(flag) cout<<"1\n";
	}
}

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

1번이 주인공이고, 1번이 꼭 되야 한다. 1번이 되야하니(x1 || x1)조건을 추가해준다.

바로 위 코드에 adj[oppo(1)].push_back(1); 를 추가해주자.