Problem

Description

给定一个$n$个点，$m$条边的有向无环无重边图。

求判断若一条边$edge$翻转后，强连通分量数量是否变化。

$1\le N \le 1000$

$1 \leq M \leq 200,000$

Input

$N$ $M$

$u_1$ $v_1$

……

$u_m$ $v_m$

Output

$M$​ lines

same or diff

Sample Input

5 9
3 2
3 1
4 1
4 2
3 5
5 3
3 4
1 2
2 5

Sample Output

same
same
same
same
same
diff
diff
diff
diff

HINT

Atcoder跑得飞快

Solution

Analysis

考虑一条边$u$​->$v$​什么时候会变，考虑忽略这条边

• 1.$v$可到达$u$
• 2.$v$可到达$u$

以上两者条件当且仅当满足一个条件强连通分量就会变化

考虑如何计算

(1) 直接记录对于每个点$v$可到达的所有点$u$；

(2) 考虑强制走第一条边

​ 记录每个点首先来自于哪个点

​ $p$：$v_1…v_k$​

​ $q$：$v_k…v_1$

​ 如果$p$和$q$相同，表示这是唯一一条边，如果忽略这条边，二者将不可达。

Attention

$O(nm)$

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define il inline
using namespace std;
const int N=1010,M=200100;

vector<int> e[N];
struct node{
    int u,v;
} g[M];

int vis[N][N],p[N][N],q[N][N];

il void dfs1(int u,int *a){
    a[u]=1;
    for(register unsigned i=0;i<e[u].size();++i){
        if(a[e[u][i]]) continue;
        dfs1(e[u][i],a);
    }
}
il void dfs(int u,int *a,int w){
    a[u]=w;
    for(register unsigned i=0;i<e[u].size();++i){
        if(a[e[u][i]]) continue;
        dfs(e[u][i],a,w);
    }
}

int n,m;

int main(){
    scanf("%d%d",&n,&m);
    rep(i,1,m){
        scanf("%d%d",&g[i].u,&g[i].v);
        e[g[i].u].push_back(g[i].v);
    }
    rep(u,1,n){
        dfs1(u,vis[u]);
        p[u][u]=q[u][u]=u;
        for(register unsigned i=0;i<e[u].size();++i){
            if(p[u][e[u][i]]) continue;
            dfs(e[u][i],p[u],e[u][i]);
        }
        reverse(e[u].begin(),e[u].end());
        for(register unsigned i=0;i<e[u].size();++i){
            if(q[u][e[u][i]]) continue;
        dfs(e[u][i],q[u],e[u][i]);
        }
    }
    rep(i,1,m){
        if(vis[g[i].v][g[i].u]^(p[g[i].u][g[i].v]!=q[g[i].u][g[i].v])) puts("diff");
        else puts("same");
    }
    return 0;
}