全体集合

题目描述：

给出 n 个点 m条边 的无向图，给出 k 个点，这 k 个点上每个点都有一个人，每个人每回合能走到一个相邻的节点（不能停留不走），问：有没有可能在某一个回合，让这些人都集中在一个点？

思路：

我们可以用黑白染色法对整个图进行染色

• 如果能够染色成功，说明每次移动都是从一种颜色走到另一种颜色，如果这些人所在的点的颜色不同，则永远无法集中到一个点去，否则是可以走到的，假设要到达的点的位置是p，k个点距离p点的距离为d[1],d[2]...d[k]，则我们只需要让每个人走lcm(d[1], d[2], ..., d[k])步就能走到p点
• 如果不能染色成功，也就说明不是二分图，也就是存在奇环，我们可以给每个点走一次奇环，就能改变他的颜色，也就能保证一定可以使得每个点的颜色都相同，也就一定能满足使得所有人都集中在一个点

所以我们只需要先判断一下是不是二分图，如果不是二分图则满足要求，如果是二分图，且k个点的颜色都是相同的，则满足条件，否则不满足

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x, y;
vector<int>G[MAX];
bool vis[MAX];
int col[MAX];
bool p;
void dfs(int u){
    vis[u] = 1;
    for(auto v : G[u]){
        if(!vis[v]){
            col[v] = col[u] ^ 1;
            dfs(v);
        }
        else {
            if(col[u] == col[v])p = 0;
        }
    }
}

void work(){
    cin >> n >> m >> k;
    p = 1;
    for(int i = 1; i <= m; ++i){
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i = 1; i <= n; ++i){
        if(!vis[i]){
            col[i] = 1;
            dfs(i);
        }
    }
    if(!p)cout << "YES\n";
    else{
        cin >> x;
        y = col[x];
        bool cao = 1;
        for(int i = 2; i <= k; ++i){
            cin >> x;
            if(y != col[x])cao = 0;
        }
        if(cao)cout << "YES\n";
        else cout << "NO\n";
    }
}


int main(){
    io;
    work();
    return 0;
}

E. Split Into Two Sets

题目描述：

给定 n(n≤2∗105,n%2=0) 个骨牌，第 i 个骨牌上有 a[i],bi 两个数字。

现在你需要把骨牌分成两堆，使得每一个堆里面都没有重复的数字。问是否可以分成两堆

思路：

显然如果某个骨牌正反两面都写了相同的数字则一定无法成功

而且如果某个数字出现的次数超过两次，根据鸽巢原理，一定会存在两个相同的数字出现在同一堆里面

我们可以开一个vector记录每个数字出现的位置i，对于每个相同的数字，我们把两个位置i,j连一条边，然后去跑二分图即可

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define io ios::sync_with_stdio(false)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, op;
int x, y;
vector<int>tr[MAX];
vector<int>G[MAX];
bool p;
int col[MAX];
bool vis[MAX];

void init(){
    p = 1;
    for(int i = 1; i <= n; ++i){
        tr[i].clear();
        G[i].clear();
        col[i] = -1;
        vis[i] = 0;
    }
}

void dfs(int u){
    vis[u] = 1;
    for(auto v : G[u]){
        if(!vis[v]){
            col[v] = col[u] ^ 1;
            dfs(v);
        }
        else {
            if(col[u] == col[v])p = 0;
        }
    }
}

void work(){
    cin >> n;
    init();
    for(int i = 1; i <= n; ++i){
        cin >> x >> y;
        if(x == y){
            p = 0;
            continue;
        }
        tr[x].push_back(i);
        tr[y].push_back(i);
    }
    for(int i = 1; i <= n; ++i){
        if(tr[i].size() != 2)p = 0;
    }
    if(!p){
        cout << "NO\n";
        return;
    }
    for(int i = 1; i <= n; ++i){
        int u = tr[i].front(), v = tr[i].back();
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int i = 1; i <= n; ++i){
        if(!vis[i]){
            col[i] = 0;
            dfs(i);
        }
    }
    if(p)cout << "YES\n";
    else cout << "NO\n";
}


int main(){
    io;
    int tt;cin>>tt;
    for(int _t = 1; _t <= tt; ++_t){
        work();
    }
    return 0;
}

E. Cars

题目描述：

在数轴上有n辆车，每辆车都有一个初始位置和方向，所有车的速度是任意的，且不为0，我们认为两辆车一定能相遇，则认为是相关联的，如果一定不能相遇则是不良关联的，相遇后不影响正常行驶

现在给你m个关系，表示两辆车是否相关联，如果相关，问你能不能构造出一种满足所有关系的情况，可以的话请输出每辆车的初始位置和方向

思路：

由于速度不一定且是题目说的是一定，所以如果一定能相遇，只能是两个相对着的车，如果一定不能相遇，则只能是两个背道而驰的车

我们可以发现，无论是有关联还是没关联，车的方向都是相反的，我们可以建图跑二分图，如果不是二分图就不存在，如果是二分图的话，只能说明可以分成两个集合，满足题目的关系要求，但是不一定在位置上是存在这样的情况的，毕竟每个位置最多只能放一个车

我们假设二分图的A集合的车子都是往左走的，col计作1，B集合的车子都是往右走, col 计作0，我们枚举所有的边op u v

• op==1，代表u和v是无关联的，我们让col[u]是1，如果不是，我们只需要交换一下u和v就行，此时由于我们假设col=1的点往左走，再加上u和v是无关联的，我们假设dis[i]表示i在数轴的位置，我们可以得到dis[u]<dis[v]
• op==2，代表u和v是有关联的，还是和上面一样，我们假设col[u]=1,也就是u是在A集合的，是往左走，我们就要满足dis[u] > dis[v]

这样其实对每种关系有了一种偏序关系，类似于差分约束其实，我们可以参考建图方式，即跑最长路，转换成以大于号，则op=1的时候是dis[v] >= dis[u] + 1,从u到v建一条长度为1的边，op=2的时候，是dis[u]>=dis[v] + 1，从v到u建一条长度为1的边，但是我们不能跑差分约束，因为我们不能知道谁在前谁在后，也就是不能通过0<=sum[i] - sum[i-1]<=1来建边来满足谁先谁后的顺序

但是我们可以通过拓扑排序来求解，根据出队顺序作为数轴的位置，必须要保证拓扑排序跑完后一定能跑通整个图

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x;
struct ran{
    int x, y, op;
}tr[MAX];
vector<int>G[MAX];
bool vis[MAX];
int col[MAX];
bool p = 1;

void dfs(int u){
    vis[u] = 1;
    for(auto v : G[u]){
        if(!vis[v]){
            vis[v] = 1;
            col[v] = col[u] ^ 1;
            dfs(v);
        }
        else {
            if(col[v] == col[u])p = 0;
        }
    }
}

int du[MAX];
int ans[MAX];
void topu(){
    queue<int>q;
    for(int i = 1; i <= n; ++i){
        if(du[i]==0)q.push(i);
    }
    int num = 0;
    while(!q.empty()){
        int u = q.front();q.pop();
        ans[u] = ++num;
        for(auto v : G[u]){
            --du[v];
            if(du[v] == 0)q.push(v);
        }
    }
    if(num == n){
        cout << "YES\n";
        for(int i = 1; i <= n; ++i){
            cout << (col[i] ? 'L' : 'R') << ' ' << ans[i] << endl;
        }
    }
    else cout << "NO\n";
}

void work(){
    cin >> n >> m;
    for(int i = 1; i <= m; ++i){
        cin >> tr[i].op >> tr[i].x >> tr[i].y;
        G[tr[i].x].push_back(tr[i].y);
        G[tr[i].y].push_back(tr[i].x);
    }
    for(int i = 1; i <= n; ++i){
        if(!vis[i]){
            col[i] = 1;
            dfs(i);
        }
    }
    if(p == 0){cout << "NO\n";return;}
    for(int i = 1; i <= n; ++i)G[i].clear();
    for(int i = 1; i <= m; ++i){
        if(col[tr[i].x] == 0)
        if(tr[i].op == 1){
            ++du[tr[i].y];
            G[tr[i].x].push_back(tr[i].y);
        }
        else {
            ++du[tr[i].x];
            G[tr[i].y].push_back(tr[i].x);
        }
    }
    topu();
}


int main(){
    io;
    work();
    return 0;
}