Codeforces Round #317 [AimFund Thanks-Round](Div.1) C. CNF 2 무방향도 찾기 루프

C. CNF 2
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
'In Boolean logic, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of clauses, where a clause is a disjunction of literals' (cited from https://en.wikipedia.org/wiki/Conjunctive_normal_form)
In the other words, CNF is a formula of type , where & represents a logical "AND"(conjunction),  represents a logical "OR"(disjunction), and vij are some boolean variables or their negations. Each statement in brackets is called a clause, and vij are called literals.
You are given a CNF containing variables x1, ..., xm and their negations. We know that each variable occurs in at most two clauses (with negation and without negation in total). Your task is to determine whether this CNF is satisfiable, that is, whether there are such values of variables where the CNF value is true. If CNF is satisfiable, then you also need to determine the values of the variables at which the CNF is true.
It is guaranteed that each variable occurs at most once in each clause.
Input
The first line contains integers n and m (1 ≤ n, m ≤ 2·105) — the number of clauses and the number variables, correspondingly.
Next n lines contain the descriptions of each clause. The i-th line first contains first number ki (ki ≥ 1) — the number of literals in the i-th clauses. Then follow space-separated literals vij (1 ≤ |vij| ≤ m). A literal that corresponds to vij is x|vij| either with negation, if vij is negative, or without negation otherwise.
Output
If CNF is not satisfiable, print a single line "NO"(without the quotes), otherwise print two strings: string "YES"(without the quotes), and then a string of m numbers zero or one — the values of variables in satisfying assignment in the order from x1 to xm.
Sample test(s)
input
2 2
2 1 -2
2 2 -1
output
YES
11
input
4 3
1 1
1 2
3 -1 -2 3
1 -3
output
NO
input
5 6
2 1 2
3 1 -2 3
4 -3 5 4 6
2 -6 -4
1 5
output
YES
100010
Note
In the first sample test formula is . One of possible answer is x1 = TRUE, x2 = TRUE.
제목의 뜻, 제시와 형식, 각 자명은 일부 또는 식을 포함하고 각 조건은 한 자구에 한 번만 나타나며 모든 자구에서 x와 ~x는 최대 두 번만 나타난다. 각 조건의 진위를 구성하여 전체와 형식이 성립되도록 요구한다.
이 문제의 관건은 자구마다 이 조건이 두 번만 나오는 데 있다.만약 x만 나타나거나 ~x만 나타나면 간단하다. 진위를 직접 확인하면 된다.만약에 x도 나타났고 ~x도 나타났다면 우리는 이렇게 할 수 있다. 자구를 점으로 보고 조건 x~x를 변으로 보고 각 점마다 최소한 한 개의 입변이 있어야 한다.이렇게 x와 ~x의 무방향변을 연결한다.만약 나무라면 틀림없이 해가 없을 것이다. 왜냐하면, 변이 점수보다 적기 때문에, 언젠가는 한 점이 가장자리에 들어가지 않아서 성립될 수 없기 때문이다.만약 나무가 아니었다면 반드시 해가 존재했을 것이다. 왜냐하면 고리 위의 가장자리에서 아무거나 하나를 꺼내서 가장자리가 되면 모든 점에 가장자리가 있기 때문이다.
이 문제는 고리 위의 가장자리를 찾는 무방향도의 문제로 바뀌었다.
무방향도에서 고리가 있는지 없는지를 어떻게 확인할 수 있을까, 두 가지 방법,
1.
첫 번째 단계: 모든 도 <=1의 정점과 관련된 모서리를 삭제하고 이 모서리와 관련된 다른 정점의 도를 1로 줄인다.
2단계: 도수가 1이 된 정점을 대기열에 배열하고 이 대기열에서 정점을 꺼내 1단계를 반복한다.
마지막으로 삭제되지 않은 정점이 있으면 루프가 존재하고 그렇지 않으면 루프가 없습니다.
2.깊이 파고들어 이미 방문한 점을 찾으면 바로 링이다. 그러나 주의해라. 한 변이 될 수 없다. 예를 들어 1-2 2-1이다. 이것은 한 변이고 링이 없다. 해결 방법은 바로 가장자리를 표시하고 지난번의 변과 같은 쪽이 아니면 된다.
도구환이 있으면 토폴로지 서열이 강하고 연결 분량이 2보다 크면 구할 수 있다.
첫 번째 방법은 가장자리, 삭제점, 복잡도를 set 우선 대기열로 최적화하고 복잡도가 O(n*log(n)에 도달해야 하기 때문이다.
이 문제에서 1과 유사한 알고리즘을 사용하여 모든 도수가 작은 것을 먼저 확정하고 도수가 큰 변을 확정한다. 만약에 풀이가 있으면 반드시 찾을 수 있고 풀지 않으면 자연히 찾을 수 없다. 복잡도는 o(n*log(n)이다.코드가 매우 간단하다

#define N 400005
#define M 400005
#define maxn 205
#define MOD 1000000000000000007
int n,m,k,t;
bool vis[N],ans[N];
int v[M];
set<int> p[N];
priority_queue<pii> q;
int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
     while(S2(n,m)!=EOF)
    {
        while(!q.empty())   q.pop();
        FI(n+1) p[i].clear();
        fill(vis,false);
        fill(ans,false);
        FI(2 * m + 2) v[i] = -1;
        FI(n){
            S(k);
            FJ(k){
                S(t);
                v[t + m] = i;
                p[i].insert(t+m);
            }
            q.push(mp(-p[i].size(),i));
        }
        bool flag = true;
        while(!q.empty()){
            int top = q.top().second;
            q.pop();
            if(vis[top]) continue;
            if(p[top].empty()){
                flag = false;
                break;
            }
            int x = *p[top].begin();
            vis[top] = true;
            ans[x] = true;
            int y = m + m - x;
            if(v[y] != -1 && !vis[v[y]]){
                p[v[y]].erase(y);
                q.push(mp(-p[v[y]].size(),v[y]));
            }
        }
        if(flag){
            printf("YES
");
            For(i,m+1,m+m+1)
                if(!ans[i])  printf("0");
                else printf("1");
            printf("
");
        }
        else {
            printf("NO
");
        }
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

두 번째 방법은 DFS로 고리를 찾고 고리의 가장자리를 찾은 후 BFS로 이 고리가 있는 연결 분량의 모든 가장자리를 확정한다.만약에 x~x만 나타난다면 직접 변을 확정하여 전체 연결분량의 다른 변을 내놓을 수 있다.복잡도는 o(n)이다.

#define N 400005
#define M 400005
#define maxn 205
#define MOD 1000000000000000007
int n,m,k,t,all,from;
int v[M],ans[N];
bool vis[N],Dvis[N];
vector<int> p[N];
queue<int> q;
void BFS(){
    while(!q.empty()){
        int top = q.front();
        q.pop();
        FI(p[top].size()){
            int g = p[top][i];
            int gx = v[g];
            if(ans[g] == -1 && ans[m + m - g] == -1){
                ans[g] = 1;ans[m + m - g] = 0;
                if(!vis[gx]){
                    q.push(gx);
                    vis[gx] = true;
                }
            }
        }
    }
}
bool DFS(int x,int fa){
    all++;
    Dvis[x] = true;
    FI(p[x].size()){
        int g = p[x][i];
        int gx = v[g];
        if((g != fa && g != m + m - fa) && ans[g] == -1 && ans[m + m - g] == -1){
            if(Dvis[gx] || vis[gx]){
                from = g;
                return true;
            }
            else if(DFS(gx,g))
            return true;
        }
    }
    return false;
}
int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
     while(S2(n,m)!=EOF)
    {
        FI(2 * m + 2) v[i] = -1,ans[i] = -1;
        fill(vis,false);
        fill(Dvis,false);
        FI(n){
            S(k);
            FJ(k){
                S(t);
                if(v[t+m] != -1){
                    vis[v[t+m]] = 1;
                    vis[i] = 1;
                    ans[t+m] = 1;
                }
                else
                    v[t + m] = i;
            }
        }
        For(i,m + 1,m + m + 1){
            if(v[i] >= 0 && v[m + m - i] >= 0){
                int s = v[i],e = v[m + m -i];
                p[s].push_back(m + m - i);
                p[e].push_back(i);
            }
            else if(v[i] >= 0 && v[m + m - i] == -1){
                ans[i] = 1;ans[m + m - i] = 0;vis[v[i]] = true;
            }
            else if(v[i] == -1 && v[m + m - i] >= 0){
                ans[m + m - i] = 1;ans[i] = 0;vis[v[m + m - i]] = true;
            }
        }
        while(!q.empty()) q.pop();
        FI(n){
            if(vis[i]){
                q.push(i);
            }
        }
        BFS();
        bool flag = true;
        FI(n){
            if(!vis[i] && !Dvis[i]){
                from = -1;all = 0;
                DFS(i,-1);
                if(all >= 2 && from == -1)
                {
                    flag = false;
                    break;
                }
                if(from != -1){
                    ans[from] = 1;ans[m + m - from] = 0;
                    while(!q.empty()) q.pop();
                    q.push(v[from]);
                    BFS();
                }
            }
        }
        if(flag){
            printf("YES
");
            For(i,m+1,m+m+1)
                if(ans[i] == 1)  printf("1");
                else printf("0");
            printf("
");
        }
        else {
            printf("NO
");
        }
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}