글 읽기 - 정말 왜 틀린지 도저히 모르겠습니다...

tompark58981 1년 전 0

입력받는 항들과 (1 OR 1) 항을 추가한 2-SAT가 성립하는지 확인하는 방법으로 코드 짰는데 계속 틀리네요....

1 OR 1을 임의로 추가하는 코드를 빼고 배열의 크기와 출력값을 적절히 바꾼 후 2-SAT 3에 제출 해봤을때는 맞았다고 뜹니다...

배열 초기화를 잘못한건가요...? 아니면 풀이 방식이 아예 틀린걸까요...ㅠ

#include<iostream>
#include<string.h>
#include<stack>
#include<vector>
using namespace std;

vector<vector<int>> v(2010);
vector<vector<int>> r(2010);
stack<int> s;
bool visited[2010],flag;
int n,m,comp[2010];

void dfs(int x){
    visited[x] = true;

    for(auto u:v[x]){
        if(visited[u]) continue;
        dfs(u);
    }

    s.push(x);
}

void rdfs(int x,int num){
    if(flag) return;

    visited[x] = true;

    for(auto u:r[x]){
        if(visited[u]) continue;
        rdfs(u,num);
    }

    if(comp[2*n-x]==num){
        flag = true; return;
    }

    comp[x] = num;
}

void init(){
    v.clear(); v.resize(2010);
    r.clear(); r.resize(2010);
    memset(visited,0,sizeof(visited));
    memset(comp,0,sizeof(comp));
    while(!s.empty()) s.pop();
    flag = false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    while(!cin.eof()){
        cin >> n >> m;

        init();

        for(int i=0;i<m;i++){
            int a,b;
            cin >> a >> b;

            v[n-a].push_back(n+b);
            v[n-b].push_back(n+a);
            r[n+b].push_back(n-a);
            r[n+a].push_back(n-b);
        }
        
        v[n-1].push_back(n+1);
        r[n+1].push_back(n-1);
        
        for(int i=0;i<=2*n;i++){
            if(visited[i]||i==n) continue;
            dfs(i);
        }

        memset(visited,0,sizeof(visited));

        int num = 1;

        while(!s.empty()){
            if(flag) break;
            int cur = s.top();
            s.pop();
            if(visited[cur]) continue;
            rdfs(cur,num);
            ++num;
        }
        
        if(flag) cout << "no\n";
        else cout << "yes\n";
    }

    return 0;
}

tompark58981 1년 전 0

while(!cin.eof()) 이걸 while(cin>>n>>m) 이걸로 바꿔주니까 맞았습니다....

c++ 문법 공부부터 해야겠네요........

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

정말 왜 틀린지 도저히 모르겠습니다...

tompark58981 1년 전 0

tompark58981 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말