DFS 간선 분류

DFS를 돌면서 그래프의 간선을 4개의 종류로 분류할 수 있다.

1. 트리 간선 (Tree Edge)

트리 간선은,  dfs 스패닝 트리 자체에 포함되는 간선을 의미한다.

간선의 확인은 u->v 에서 v가 아직 발견되지 않았다면 이 간선은 트리 간선에 포함된다.

 

2. 역방향 간선 (Back Edge)

dfs 스패닝 트리에서 이미 자손에서 조상으로 향하는 간선을 의미한다.

위 그림에서 자손 D에서 조상 A로 향하는 간선을 보면, 아직 A를 종료하지 않은 상태에서 D가 A로 가려고 한다.

간선의 확인은 u->v 에서 v가 아직 종료되지 않았으면 이 간선은 역방향 간선에 포함된다.

 

역방향 간선의 존재는 사이클의 존재와 동치이다.

 

3. 순방향 간선 (Forward Edge)

dfs 스패닝 트리에서 조상에서 자손으로 향하는 간선을 의미한다.

위 그림에서는 조상 A에서 자손 D로 향하는 간선을 보면 D는 종료되었지만, A의 방문 순서가 D보다 더 빠름을 알 수 있다.

간선의 확인은 u->v 에서 v가 종료되었으며, u가 v보다 빨리 발견되었다면 이 간선을 순방향 간선이다.

 

4. 교차 간선 (Cross Edge)

위 3가지 분류에 모두 해당되지 않는 간선이 바로 교차 간선이다.

간선의 확인은 u->v 에서 v가 종료되었으며, v가 u보다 빨리 발견되었다면 이 간선은 교차 간선이다.

 

 

만약 그래프가 무향 그래프라면, 순방향간선과 역방향간선이 같으며, 교차 간선은 존재하지 않는다.

즉, 역방향 간선과 트리 간선만 존재한다고 생각해도 된다.

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int n, m;
vector<int> adj[MAXN+10];

int vis[MAXN+10]; //0 : not visited , 1 : visited but not ended , 2 : visited and ended
int dis[MAXN+10], cnt=1; //order of discover

void dfs(int now)
{
    vis[now]=1; dis[now]=cnt++;
    for(int nxt : adj[now])
    {
        if(vis[nxt]==0)
        {
            printf("%d %d : tree\n", now, nxt);
            dfs(nxt);
        }
        else if(vis[nxt]==1)
        {
            printf("%d %d : back\n", now, nxt);
        }
        else if(dis[now]<dis[nxt])
        {
            printf("%d %d : forward\n", now, nxt);
        }
        else if(dis[now]>dis[nxt])
        {
            printf("%d %d : cross\n", now, nxt);
        }
    }
    vis[now]=2;
}

int main()
{
    int i, j;

    scanf("%d%d", &n, &m);
    for(i=1; i<=m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        adj[u].push_back(v);
    }

    dfs(1);
}