题目描述
有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也是旗鼓相当的。也就是说，若干个旗鼓相当的人组成了一个群体，群体之内任意两个人是旗鼓相当的，不同群体的任意两个人肯定不是旗鼓相当的。
现在，对于每一场比赛，星见班长想知道，如果这场比赛的胜负改变了的话，群体情况会不会也跟着发生改变。群体情况改变，当且仅当存在两个人，一开始在一个群体，胜负改变后不在一个群体；或者一开始不在一个群体，胜负改变后在一个群体。
注：出题人被咕了导致大数据丢失且该题有O（n^2）的做法
输入
第一行两个正整数n,m，表示有n个人和m场比赛
接下来m行，每行两个正整数a,b描述一场比赛，这场比赛中a击败了b
输出
m行，每行一个字符串表示这场比赛胜负改变后群体情况会不会改变
改变输出”diff”，不改变输出”same”(不包括引号)
样例输入
复制样例数据
3 3
1 2
1 3
2 3
样例输出
same
diff
same
提示
对于所有数据，满足2 ≤ n ≤ 103 , 1 ≤ m ≤ 2 ∗ 105，没有两次比赛参加的人相同，胜负也相同
Subtask1[31pts] n ≤ 100,m ≤ 500
Subtask2[12pts] m = n − 1，保证把有向边看作无向边后，原图联通
Subtask3[17pts] m = n，保证把有向边看作无向边后，原图联通
Subtask4[18pts] m ≤ 5000
Subtask5[22pts] 无特殊限制
题目就是让判断在原图中 ， 如果把某条边反向之后 ， 其两点关系是否发生变化 :
反转之前可能两点在一个环里面， 亦或者不在一个环里面， 反转之后也应该是这种状态（在亦或者不再同一环中）；
两个点在一个环里面：有向边<u , v> , 可以从v 到达 u ， 再加上原本u 可以到达v ， 就组成一环
然后判断两点之间是否有环 ， 我们可以直接用深搜，从v点搜索， 看是否能够到达u点
主函数里面我们可以先搜索一下反向之前 v 是否可以到达 u ，dfs(v , u) ，然后加一条反向边（v， u）， 同时把u->v 标记一下不能用了， 接着搜索一下能否从u 到达v ,
dfs(u , v) ，两者都可以到达， 即"same" , 否则"diff"
学到了怎么对一个图去掉边， 也就是直接设置一个变量， 标志此边能否使用
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10 ;
int n , m , a , b , vis[N] , idx ;
struct node
{
int u , v , ne ;
bool enable ;
}e[N];
int h[N] ;
int add(int a , int b)
{
e[++ idx].u = a , e[idx].v = b , e[idx].ne = h[a] , h[a] = idx , e[idx].enable = true ;
return idx ;
}
bool found ;
void dfs(int u , int pos)
{
if(vis[u]) return ;
vis[u] = true ;
if(u == pos)
{
found = true ;
return ;
}
for(int i = h[u] ;i != -1 ;i = e[i].ne)
{
int v = e[i].v ;
if(!e[i].enable) continue ;
dfs(v , pos) ;
if(found) return ;
}
return ;
}
int main()
{
scanf("%d%d" , &n , &m) ;
// int a , b ;
memset(h , -1 , sizeof h) ;
for(int i = 1 ;i <= m ;i ++)
scanf("%d%d" , &a , &b) , add(a , b) ;
for(int i = 1 ;i <= m ;i ++)
{
// 第i条边为 u -> v
memset(vis , false , sizeof vis) ;
found = false ;
dfs(e[i].v , e[i].u) ; // 第一次搜索v 能否到达 u
bool temp1 = found ;
found = false ;
memset(vis , false , sizeof vis) ;
int t = add(e[i].v , e[i].u) ; // 加上v->u 这条边 ， t 是为了下面再次删点这个边做准备，
e[i].enable = false ; // 删掉 u->v 这条边
dfs(e[i].u , e[i].v) ; // 第二次搜索u 能否到达 v
bool temp2 = found ;
if(temp1 == temp2) puts("same") ;
else puts("diff") ;
e[t].enable = false ; // 删掉v , u ,这条边
e[i].enable = true ; // 最后为了不影响 下一条边的判断 ， 再将u->v 这条边加上
}
return 0 ;
}