BUPT校内训练&CodeChef - VRTXCOVR-Vertex Cover 2-SAT

文章来自  Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

Description

You are given an undirected graph G = (V, E) containing N nodes and M edges. The nodes are numbered from 1 to N. A subset C of V is a vertex cover if for every edge (u, v) ∈ E, at least one of u and v belong to C. Note that C = V is always a vertex cover.
Consider a partition of V into two sets A and B. It is said to be a valid partition, if the following two conditions are satisfied: A should be a vertex cover. And for each i such that 1 ≤ i ≤ n/2, nodes 2i and 2i - 1 don't belong to the same set (i.e. one belongs to set A and the other to set B).
Determine if a valid partition exists. If it exists, provide an example of one valid partition.

Input

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space-separated integers N and M denoting the number of nodes and number of edges in the graph respectively.
Each of the following M lines contains two space-separated integers u and v denoting an edge between nodes u and v.

Output

For each test case, print a line containing the string "possible" (without quotes) if a solution exists or "impossible" otherwise.
If a solution exists, print a second line containing a binary string. The i-th character of this string should be '0' if vertex i is in set B or '1' if it is in set A.

Constraints

1 ≤ T ≤ 10^5
1 ≤ N ≤ 2 · 10^5
0 ≤ M ≤ 2 · 10^5
1 ≤ u, v ≤ N
1 ≤ sum of N over all test cases ≤ 10^6
1 ≤ sum of M over all test cases ≤ 10^6

Example

Input

2
3 2
1 2
2 3
4 5
1 3
2 4
1 4 
1 2
2 3

Output

possible
011
impossible

Explanation

Example case 1: We can put nodes numbered 2 and 3 in set A and node 1 in set B. Note that this is a valid partition because set A is a vertex cover; also, nodes numbered 1 and 2 belong to different sets.
Example case 2: There exists no partition which satisfies the conditions.

题目大意

给一个无向图G=(V,E),让你将节点分为两个集合A,B,使得满足对于一个整数i,节点2i与节点2i-1不在同一个集合内,并且满足A,B为两个合法的点覆盖(点覆盖的定义请读英文或者自行百度)。要求输出分配方案。


题解

这是一个标准的2-SAT问题
我们可以把问题看成这样:0代表不选中进入A,1代表选中进入A,这就很符合2-SAT问题的模型了。
至于建图,就是对于数据中的边的连接,我们建立a or b = 1的这种边连接,对于限制条件,我们建立2i xor 2i- 1 = 1的这种边关系,然后tarjan判断是否存在可行解,tarjan缩点后利用topsort(拓扑排序)求出任意一组可行解。
注意:本题目在初始化时不能使用memset,很可能会超时。


代码

#include 
using namespace std;
const int maxn = 2e5+5;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' ||  c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = num * 10 + c - '0';
    return (flag ? -1 : 1) * num;
}
vector<int>g1[maxn<<1];
vector<int>g2[maxn<<1];
int dfs_time;
int dfn[maxn<<1],low[maxn<<1],ins[maxn<<1],scc[maxn<<1],scc_cnt,ind[maxn<<1],opp[maxn<<1];
int color[maxn<<1];
stacks;
int n,t,m;
int u,v;
void init(){
    dfs_time = 0;
    for(int i = 1;i <= 2*n;++i){
        dfn[i] = low[i] = scc[i] = ind[i] = ins[i] = opp[i] = 0;
        color[i] = -1;
    }
    for(int i = 1;i <= 2*n;++i)
        g1[i].clear();
    for(int i = 1;i <= scc_cnt;++i)
        g2[i].clear();
    scc_cnt = 0;
    while(!s.empty())
        s.pop();
    return;
}
void tarjan(int u){
    dfn[u] = low[u] = ++dfs_time;
    s.push(u);ins[u] = 1;
    for(int i = 0;i < g1[u].size();++i){
        int v = g1[u][i];
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[u],low[v]);
        }
        else if(ins[v])low[u] = min(low[u],dfn[v]);
    }
    if(dfn[u] == low[u]){
        int now;
        scc_cnt++;
        do{
            now = s.top();
            s.pop();
            ins[now] = 0;
            scc[now] = scc_cnt;
        }while(now != u);
    }
    return;
}
void top_sort(){
    queueq;
    for(int i = 1;i <= scc_cnt;++i){
        if(!ind[i])q.push(i);
    }
    while(!q.empty()){
        int u = q.front();
        q.pop();
        if(color[u] == -1){
            color[u] = 1;
            color[opp[u]] = 0;
        }
        for(int i = 0;i < g2[u].size();++i){
            int v = g2[u][i];
            --ind[v];
            if(!ind[v])q.push(v);
        }
    }
    return;
}
int main(){
    t = get_num();
    while(t--){
        n = get_num();
        m = get_num();
        init();
        for(int i = 1;i <= m;++i){
            u = get_num();
            v = get_num();
            g1[u+n].push_back(v);
            g1[v+n].push_back(u);
        }
        for(int i = 1;i <= n;i += 2){
            if(i == n)break;
            g1[i].push_back(i+1+n);
            g1[i+1].push_back(i+n);
            g1[i+n].push_back(i+1);
            g1[i+1+n].push_back(i);
        }
//        cout << n << endl;
        for(int i = 1;i <= 2*n;++i)
            if(!dfn[i])tarjan(i);
        bool flag = true;
        for(int i = 1;i <= n;++i){
            if(scc[i] != scc[i+n]){
                opp[scc[i]] = scc[i+n];
                opp[scc[i+n]] = scc[i];
            }
            else {
                flag = false;
                break;
            }
        }
        if(flag)
            printf("possible\n");
        else{
            printf("impossible\n");
            continue;
        }
        for(int i = 1;i <= 2*n;++i){
            int u = scc[i];
            for(int j = 0;j < g1[i].size();++j){
                int v = scc[g1[i][j]];
                if(u == v)continue;
                g2[v].push_back(u);
                ind[u]++;
            }
        }
        top_sort();
        for(int i = 1;i <= n;++i){
            if(color[scc[i]] == 1)printf("1");
            else printf("0");
        }
        printf("\n");
    }
    return 0;
}​
Sign in to leave a comment.
No Leanote account ? Sign up now.
0 comments
Title - Artist
0:00