Codeforces Round #541 (Div. 2) D（并查集+拓扑排序） F （并查集）

D. Gourmet choice

链接：http://codeforces.com/contest/1131/problem/D

思路： =  的情况我们用并查集把他们扔到一个集合，然后根据 > < 跑拓扑排序，根据拓扑排序的结果从小到大填数字就好了，需要注意的细节写在代码注释里了

代码：

#include<bits/stdc++.h>
using namespace std;
const int M = 2e3+10;
int f[M],n,m;
set<int>st[M];
vector<int>v;
int vis[M];
map<int,int>ans;
bool flag;
string g[M];
int in[M];
int Find(int x){
    if(x == f[x]) return x;
    return f[x] = Find(f[x]);
}

int Union(int x,int y){
    int fx = Find(x);
    int fy = Find(y);
    if(fx != fy) f[fx] = fy;
}

void Toposort(){
    queue<int>q;
    for(int i = 0;i < n+m;i ++){
    //同一个集合内的数如果之前已经出现过就跳过
        if(vis[Find(i)]==1) continue;
        if(in[Find(i)] == 0){
            q.push(Find(i));
            vis[Find(i)]=1;
        }
    }
    //因为要计数，所以多开一个vector存每一轮入度为0的点
    int cnt = 1;
    while(!q.empty()){
        v.clear();
        while(!q.empty()){
            v.push_back(q.front());
            q.pop();
        }
        for(auto &i : v){
            ans[i] = cnt;
            for(auto &j : st[i]){
                if(vis[j]==1) continue;
                in[j]--;
                if(in[j] == 0){
                    q.push(j);
                    vis[j]=1;
                }
            }
        }
        cnt ++;
    }
}

int main()
{
    cin>>n>>m;
    flag = 1;
    for(int i = 0;i < n+m;i ++) f[i] = i;
    for(int i = 0;i < n;i ++){
        cin>>g[i];
        for(int j = 0;j < m;j ++){
            if(g[i][j] == '='){
                if(Find(i) != Find(n+j))
                    Union(i,n+j);
            }
        }
    }
     for(int i = 0;i < n;i ++){
        for(int j = 0;j < m;j ++){
            if(g[i][j] == '=') continue;
            int x = Find(i),y = Find(n+j);
            if(x == y) flag = 0;
            if(g[i][j] == '>') swap(x,y);
            if(st[x].find(y) == st[x].end()){
                st[x].insert(y);
                in[y]++;
            }
        }
    }
    //如果一个集合内出现>或<,那么自相矛盾，输出No
    if(!flag){
        cout<<"No"<<endl;
        return 0;
    }
    Toposort();
    //如果两个数 < > 关系矛盾，也就是i出现x>y且x<y,那么双方入度都无法为0，无法取值，
    //所以如果值为0那么代表出现矛盾的情况输出N0
    for(int i = 0;i < n+m;i ++){
        if(ans[Find(i)] == 0)
            flag = 0;
    }
    if(flag){
        cout<<"Yes"<<endl;
        for(int i = 0;i < n;i ++)
            cout<<ans[Find(i)]<<" ";
        cout<<endl;
        for(int i = n;i < n+m;i ++)
            cout<<ans[Find(i)]<<" ";
        cout<<endl;
    }
    else cout<<"No"<<endl;
    return 0;
}

F. Asya And Kittens

链接：http://codeforces.com/contest/1131/problem/F

思路：很容易发现房间合并的过程非常像并查集集合的合并，但是并查集合并并不能得到一段序列，所以我们用一个nex数组储存数字的前后关系，并用last数组记录集合最后的那个数，两个集合合并时，左边集合最后那个数的nex就是右边集合的第一个数，合并后整个集合的last就是右边集合的last，这样维护好两个数组，最后遍历一遍nex数组就可以得到一段符合要求的序列了。

实现代码：

#include<bits/stdc++.h>
using namespace std;
const int M = 2e5+10;
int f[M],nex[M],last[M];
int Find(int x){
    if(x == f[x]) return x;
    return f[x] = Find(f[x]);
}

int Union(int x,int y){
    int fx = Find(x);
    int fy = Find(y);
    if(fx != fy) f[fy] = fx;
}

int main()
{
    int n,a,b;
    cin>>n;
    for(int i = 1;i <= n;i ++)
        last[i]=f[i]=i;
    for(int i = 1;i <= n-1;i ++){
        cin>>a>>b;
        int fx = Find(a);
        int fy = Find(b);
        nex[last[fx]] = fy;
        last[fx] = last[fy];
        Union(a,b);
    }
    for(int i = Find(1);i;i=nex[i])
        cout<<i<<" ";
    return 0;
}