icontofig | 发布于 2019-02-07 01:05:31 | 阅读量 421 | 2-SAT tarjan topsort

## 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

```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.

## 代码

```#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;
}﻿​```

421 人读过

0 条评论