절단선 찾기 vs 싸이클 찾기

절단점 찾는 알고리즘과 싸이클 찾은 알고리즘은 둘다 DFS방식을 이용하지만, 미묘하게 다르다..

뭐가 다를까?.

절단선 = 단절선. (Bridge : 단절선)

int dfs(int A, int parent) : A와 A의 자식 노드가 A에서 parent노드로 가는 간선을 사용하지 않고 도달할 수 있는 정점 중 가장 먼저 dfs함수가 방문한 정점을 반환한다.

<절단선 찾기>

static int dfs(int s, int p, int d) {  // start, parent, depth D[s]=d; int ck = d; for (Object des : list[s]) { Node nd = (Node)des; if(nd.e==p) continue; if(D[nd.e]==0) { int re = dfs(nd.e, s, d+1); if(re>D[s]) { res.add(nd.id); } ck = Math.min(re, ck); } else { ck = Math.min(ck, D[nd.e]); } } return ck; }

< 싸이클 찾기 > 

private static void dfs(int idx) { vis[idx] = true; int next = s[idx]; if (!vis[next]) { p[next] = idx; dfs(next); } else { if (!fin[next]) { cycle(idx, s[idx]); } } fin[idx] = true; } private static void cycle(int idx, int next) { cnt++; if (idx == next) return; cycle(p[idx], next);  }

<절단점 찾기 전체 소스>

static class Node implements Comparable<Node>{

int e;

int id;

public Node(int e, int id) {

this.e = e;

this.id = id;

}

@Override

public int compareTo(Node o) {

return this.id - o.id;

}

}

static int dfs(int s, int p, int d) {  // start, parent, depth

D[s]=d;

int ck = d;

for (Object des : list[s]) {

Node nd = (Node)des;

if(nd.e==p) continue;

if(D[nd.e]==0) {

int re = dfs(nd.e, s, d+1);

if(re>D[s]) {

res.add(nd.id);

}

ck = Math.min(re, ck);

} else {

ck = Math.min(ck, D[nd.e]);

}

}

return ck;

}

static int N, M;

static int[] D;

static List[] list;

static ArrayList<Integer> res;

public static void main(String[] args) throws IOException {

System.setIn(new FileInputStream("res/inputPre11.txt"));

long Start = System.currentTimeMillis();

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int T = Integer.parseInt(br.readLine());

StringTokenizer st;

int a, b;

for (int t = 1; t < T+1; t++) {

st = new StringTokenizer(br.readLine(), " ");

N = Integer.parseInt(st.nextToken());

M = Integer.parseInt(st.nextToken());

list = new List[N+1];

res = new ArrayList<Integer>();

D = new int[N+1];

for (int i = 1; i < M+1; i++) {

st = new StringTokenizer(br.readLine(), " ");

a = Integer.parseInt(st.nextToken());

b = Integer.parseInt(st.nextToken());

if(list[a]==null) list[a] = new ArrayList<Node>();

list[a].add(new Node(b, i));

if(list[b]==null) list[b] = new ArrayList<Node>();

list[b].add(new Node(a, i));

}

dfs(1,0,0);  // start, parent, depth

Collections.sort(res);

StringBuffer sb = new StringBuffer();

for (int i = 0; i < res.size(); i++) {

sb.append(" ");

sb.append(res.get(i));

}

System.out.println("#"+t+" "+res.size()+sb.toString());

}

System.out.println("Total : " + (System.currentTimeMillis()-Start) + " ms" );

}

< 싸이클 찾기 전체 소스 >

public class Main {

private static int[] s;

private static int[] p;

private static int n;

private static int T;

private static boolean[] vis;

private static boolean[] fin;

private static int cnt;

public static void main(String[] args) throws Exception {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

StringTokenizer st = null;

T = Integer.parseInt(br.readLine().trim());

for (int t = 1; t <= T; t++) {

n = Integer.parseInt(br.readLine().trim());

st = new StringTokenizer(br.readLine().trim());

s = new int[n + 1];

p = new int[n + 1];

vis = new boolean[n + 1];

fin = new boolean[n + 1];

cnt = 0;

for (int i = 1; i <= n; i++) {

s[i] = Integer.parseInt(st.nextToken());

}

for (int i = 1; i <= n; i++) {

if (!vis[i]) {

dfs(i);

}

}

System.out.println(n - cnt);

}

}

private static void dfs(int idx) {

vis[idx] = true;

int next = s[idx];

if (!vis[next]) {

p[next] = idx;

dfs(next);

} else {

if (!fin[next]) {

cycle(idx, s[idx]);

}

}

fin[idx] = true;

}

private static void cycle(int idx, int next) {

cnt++;

if (idx == next)

return;

cycle(p[idx], next);

} 

} 

<단절점 찾기 >

1. int dfs(int A, bool isRoot) : A의 자식 노드가 A를 거치지 않고 도달할 수 있는 정점 중 가장 먼저 dfs함수가 방문한 정점을 반환한다.

isRoot는 정점 A가 루트노드인지를 나타냅니다.

2. 정점 i가 DFS탐색에서 발견된 순서 : discovered[i]

3. 정점 i가 절단점인지 여부 : isCutVertex[i]

단절점이란 그 정점을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 정점을 말한다. 

 >  root이면서 child가  2개 이상인 경우

#include <iostream>

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXV 10010
int V, E, counter=0, discovered[MAXV];
bool isCutVertex[MAXV];
vector<int> graph[MAXV];

int dfs(int A, bool isRoot){
    discovered[A]= ++counter;
    int ret = discovered[A];
    
    int child=0; //정점 A가 루트 노드 일 경우를 대비해서 DFS스패닝 트리에서의 자식 수 세어준다.
    for(int i = 0 ;  i< (int)graph[A].size() ; i++){
        int next = graph[A][i];
        if(!discovered[next]){
            child++;
            //low : 정점 A의 자식 노드가 갈 수 있는 노드중 가장 일찍 방문한 노드
            int low = dfs(next, false);
            if(!isRoot && low >= discovered[A])
                isCutVertex[A] = true;
            ret=  min(ret, low);
        }else{
            ret = min(ret, discovered[next]);
        }
    }
    
    if(isRoot)
        isCutVertex[A] = (child >=2);
    return ret;
}

int main(){
    scanf("%d%d", &V, &E);
    for(int i =1 ; i<= E; i++){
        int a, b;
        scanf("%d%d", &a, &b);
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    for(int i = 1; i <= V; i++){
        if(!discovered[i])
            dfs(i, true);
    }

    int cnt=0;
    for(int i = 1 ; i<= V; i++){
        if(isCutVertex[i])
            cnt++;
    }
    printf("%d\n", cnt);
    for(int i =1 ; i<= V; i++){
        if(isCutVertex[i])
            printf("%d ", i);
    }
    return 0;
}