UVA796 Critical Links

Graph, 절단선

출처: UVA UVA796 Critical Links


SOL)
절단선 찾기 주석..


[-] Collapse

#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<stdio.h>
#include<sstream>
#include<algorithm>
using namespace std;

int visit[100]; //방문 여부 순위를 갖는다.
bool adj[100][100]; //인접행렬
bool edge[100][100]; //edge의 사용여부
int num, cnt;
vector<pair<int, int> > result;

void init(){
    memset(visit, -1, sizeof(visit));
    memset(edge, false, sizeof(edge));
    memset(adj, false, sizeof(adj));
    result.clear();
    cnt = 0;
}
void adjSetting(string str){
    istringstream os(str);
    string edgeNumStr;
    int u, v;
    os >> u >> edgeNumStr;
    while (os >> v){
        if (adj[u][v] == false)
            adj[v][u] = adj[u][v] = true;
    }
}
int findAP(int here){
    visit[here] = cnt++;
    //ret은 정점 here이 어려가기 간선을 돌아 최대로 올라갈 수 있는 순위를 저장
    int ret = visit[here];
    int there;
    for (int i = 0; i < num; i++){
        if (adj[here][i]) there = i;
        else continue;
        //보고있는 간선이 사용중이면 컨티뉴
        if (edge[here][there]) continue;
        if (visit[there] == -1){
            //내 자식노드가 최대로 올라갈 수 있는 번호 구하기
            edge[there][here] = edge[here][there] = true;
            int subtree = findAP(there);
            edge[there][here] = edge[here][there] = false;
            //edge[there][here],edge[here][there]을 사용 못하면
            //here까지 올라오질 못하면서 더 위로도 못간다. 이럴 경우 절단선
            if (subtree > visit[here]){
                if (here < there)
                    result.push_back(make_pair(here, there));
                else
                    result.push_back(make_pair(there, here));
            }
            //아직 방문하지 않은 어느 정점을 돌아
            //같거나 더 높은곳으로 갈 수 있는 경우 ret를 갱신
            ret = min(ret, subtree);
        }
        else  //간선은 방문 안했지만 이미 방문한 곳으로 갈 수 있는 경우
            ret = min(ret, visit[there]);
    }
    return ret;
}

int main(){
    //freopen("input.txt", "r", stdin);
    string str;
    while (cin >> num){
        getline(cin, str);
        init();
        for(int i = 0; i < num; i++){
            getline(cin, str);
            adjSetting(str);
        }
        for (int i = 0; i < num; i++){
            if (visit[i] == -1) findAP(i);
        }
        sort(result.begin(), result.end());
        cout << result.size() << " critical links" << endl;
        for (int i = 0; i < result.size(); i++)
            cout << result[i].first << " - " << result[i].second << endl;
        cout << endl;
    }
    return 0;
}