Party
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6682 Accepted Submission(s): 2194
Problem Description
有n对夫妻被邀请参加一个聚会，因为场地的问题，每对夫妻中只有1人可以列席。在2n 个人中，某些人之间有着很大的矛盾（当然夫妻之间是没有矛盾的），有矛盾的2个人是不会同时出现在聚会上的。有没有可能会有n 个人同时列席？
Input
n： 表示有n对夫妻被邀请 (n<= 1000)
m： 表示有m 对矛盾关系 ( m < (n - 1) * (n -1))
m： 表示有m 对矛盾关系 ( m < (n - 1) * (n -1))
在接下来的m行中，每行会有4个数字，分别是 A1,A2,C1,C2
A1,A2分别表示是夫妻的编号
C1,C2 表示是妻子还是丈夫 ，0表示妻子 ，1是丈夫
夫妻编号从 0 到 n -1
Output
如果存在一种情况 则输出YES
否则输出 NO
否则输出 NO
Sample Input
2
1
0 1 1 1
1
0 1 1 1
Sample Output
YES
Source
令夫为a，妻为a非
有矛盾的夫妻之间连边，不能出现在同一个强连通分量中。
//2017-08-26
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector> using namespace std; const int N = ;
const int M = N*N;
int head[N], rhead[N], tot, rtot;
struct Edge{
int to, next;
}edge[M], redge[M]; void init(){
tot = ;
rtot = ;
memset(head, -, sizeof(head));
memset(rhead, -, sizeof(rhead));
} void add_edge(int u, int v){
edge[tot].to = v;
edge[tot].next = head[u];
head[u] = tot++; redge[rtot].to = u;
redge[rtot].next = rhead[v];
rhead[v] = rtot++;
} vector<int> vs;//后序遍历顺序的顶点列表
bool vis[N];
int cmp[N];//所属强连通分量的拓扑序 //input: u 顶点
//output: vs 后序遍历顺序的顶点列表
void dfs(int u){
vis[u] = true;
for(int i = head[u]; i != -; i = edge[i].next){
int v = edge[i].to;
if(!vis[v])
dfs(v);
}
vs.push_back(u);
} //input: u 顶点编号; k 拓扑序号
//output: cmp[] 强连通分量拓扑序
void rdfs(int u, int k){
vis[u] = true;
cmp[u] = k;
for(int i = rhead[u]; i != -; i = redge[i].next){
int v = redge[i].to;
if(!vis[v])
rdfs(v, k);
}
} //Strongly Connected Component 强连通分量
//input: n 顶点个数
//output: k 强连通分量数;
int scc(int n){
memset(vis, , sizeof(vis));
vs.clear();
for(int u = ; u < n; u++)
if(!vis[u])
dfs(u);
int k = ;
memset(vis, , sizeof(vis));
for(int i = vs.size()-; i >= ; i--)
if(!vis[vs[i]])
rdfs(vs[i], k++);
return k;
} void solve(int n){
for(int i = ; i < n; i++){
if(cmp[i] == cmp[i+n]){//a和NOT a在同一个强连通分量中，布尔方程无解
cout<<"NO"<<endl;
return;
}
}
cout<<"YES"<<endl;//布尔方程有解
return;
} int main()
{
std::ios::sync_with_stdio(false);
//freopen("inputA.txt", "r", stdin);
int n, m;
while(cin>>n>>m){
init();
int u, v, a, b;
for(int i = ; i < m; i++){
cin>>u>>v>>a>>b;
if(a == && b == ){// u && v
add_edge(u+n, v);// NOT u -> v
add_edge(v+n, u);// NOT v -> u
}else if(a == && b == ){// u && NOT v
add_edge(u+n, v+n);// NOT u -> NOT v
add_edge(v, u);// v -> u
}else if(a == && b == ){// NOT u && v
add_edge(u, v);// u -> v
add_edge(v+n, u+n);// NOT v -> NOT u
}else if(a == && b == ){// NOT u && NOT v
add_edge(u, v+n);// u -> NOT v
add_edge(v, u+n);// v -> NOT u
}
}
scc(n<<);
solve(n);
} return ;
}