Contest1906 - 2019秋个人训练赛4 THE STAR KNOWS 将关系的判断通过建图去解决

这道题 是泉州市OJ上的题目，可能发不了链接，我就直接复制题目了。

有n 个人参加Revue，她们之间共进行了m 场比赛

如果在某场比赛中a 击败了b，那么a 可能胜过b

如果a 可能胜过b，b 可能胜过c，那么a 可能胜过c

如果x 可能胜过y，y 也可能胜过x，那么x 和y 是旗鼓相当的

但如果x 可能胜过y 不满足，y 可能胜过x 也不满足，那么x 和y 不是旗鼓相当的

可以发现，如果a 和b 是旗鼓相当的，b 和c 是旗鼓相当的，那么a 和c 也是旗鼓相当的。也就是

说，若干个旗鼓相当的人组成了一个群体，群体之内任意两个人是旗鼓相当的，不同群体的任意两个人肯

定不是旗鼓相当的。

现在，对于每一场比赛，星见班长想知道，如果这场比赛的胜负改变了的话，群体情况会不会也跟着

发生改变。群体情况改变，当且仅当存在两个人，一开始在一个群体，胜负改变后不在一个群体；或者一

开始不在一个群体，胜负改变后在一个群体。

Input (From File: star.in)

第一行两个正整数n,m，表示有n 个人和m 场比赛

接下来m 行，每行两个正整数a, b 描述一场比赛，这场比赛中a 击败了b

Output (To File: star.out)

m 行，每行一个字符串表示这场比赛胜负改变后群体情况会不会改变

改变输出”diff”，不改变输出”same”(不包括引号)

分析：
这道题目从题目来看，好复杂>_<，就是给你的关系当中，去判断是否可以产生不矛盾的情况；
一开始的时候想好了用并查集来着，毕竟，处理这样的关系的问题会朝向并查集这个方向去想，但是，，，没想出来，太菜了

看了一位dalao 的blog才知道，原来还可以用图建边的方式，去暴力去做，，，，实在是没有想出来，原来可以这样去处理（砸桌子中ing。。。）

其实就是用在线转离线的方式去处理，一开始将所有的这种比赛获胜与失败的关系，去建立一张有向图，然后就看，他们之间的关系是否能够相互矛盾，什么意思呢；
就是你一开始建好的图，如果是从u–>v是可到达的（或者不可到达），然后你加了一条反向边之后，如果还是可到达的（或者还是不可到达的）,那么就是说明，这两个团体没有发生改变；
依据这一思路，然后去解决就好了；

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <set>
#include <utility>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define lep(i,l,r) for(int i=l;i>=r;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queue<int,vector<int> ,greater<int> >q;
const int N = 2e5 + 10;
const int mod = 1e9+7;
int tot,head[N];
struct node{
    int from,to,pass,next;
}num[N<<3];
int add(int u,int v){
    num[tot].from=u;
    num[tot].to=v;
    num[tot].next=head[u];
    num[tot].pass=1;
    head[u]=tot++;
    return tot;
}
bool flag,tflag,vis[N];
void dfs(int pre,int dis){
    vis[pre]=true;
    if(pre==dis){
        flag=true;
        return ;
    }
    int to;
    for(int i=head[pre];i>=0;i=num[i].next){
        if(num[i].pass==0) continue;
        to=num[i].to;
        if(vis[to]) continue;
        dfs(to,dis);
        if(flag)
            return ;
    }
    return;
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif // ONLINE_JUDGE
    int n,m;
    memset(head,-1,sizeof head);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
    }
    int tflag;
    for(int i=0;i<m;i++){
        flag=false;

        for(int i=1;i<=n;i++) vis[i]=false;
        dfs(num[i].to,num[i].from);//这个地方是从反向开始找
        tflag=flag;

        flag=false;
        int NO=add(num[i].to,num[i].from);//建立反向边
        num[i].pass=0;

        for(int i=1;i<=n;i++) vis[i]=false;
        dfs(num[i].from,num[i].to);//此时起点变成终点，相当于刚建好的边来说还是反向边

        if(flag==tflag)
            printf("same\n");
        else
            printf("diff\n");
        num[i].pass=1;
        num[NO-1].pass=0;
    }
    return 0;
}

参考：https://dorbmon.live/index.php/2019/07/28/the-star-knows/

转载：https://blog.csdn.net/c___c18/article/details/101624970