5개의 댓글이 있습니다.
-
-
JongMan -
오.. cut edge 문제로군요. 이거랑 관련해서는 운좋게도 [...] 이미 비슷한 문제에 대한 튜토리얼이 올라와 있습니다.
(몇개 있지도 않은 튜토리얼 중에 잘도 .. -_-;)
http://algospot.com/zbxe/openlecture/324
를 참조하세요. ^
18년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
@,.@
문제링크 : http://acm.uva.es/p/v7/796.html
Ariculation Point 문제와 비슷하다고 생각했는데요. W.A 나오네요.ㅋ
저는 "C로 쓴 자료구조론"의 프로그램 6.4 dfnlow함수를 약간 고쳐서 생각해봤습니다.
Ariculation Point의 경우는 dfnlow함수를 돌렸을때 루트가 자식이 2개이상이거나, low(자식) >= dfn(자신) 이면 해당 돼지만, critical link의 경우는 low(자식) > dfn(자신) 이면 자식-자신 링크는 크리티컬 링크가 된다고 생각합니다.
어느 부분이 잘못된건가요? ;;
// 소스 추가합니다..;;
#include <iostream>
using namespace std;
//#include <fstream>
//fstream fin("input.txt");
//#define cin fin
const int max_node = 1000;
int nodeNum, num, startNode;
int dfn[max_node];
int low[max_node];
int link_a[max_node][max_node];
bool isVisit[max_node];
int node[max_node*max_node][2];
int ind;
void init()
{
int i;
for(i = 0; i < nodeNum; ++i)
{
isVisit[i] = false;
dfn[i] = low[i] = -1;
link_a[i][0] = 0;
}
ind = num = 0;
low[i] = -1;
}
int Min(int a, int b)
{
if(a < b)
return a;
return b;
}
void insertarray(int a, int b)
{
int temp;
if(a > b)
{
temp = b;
b = a;
a = b;
}
node[ind][0] = a;
node[ind++][1] = b;
}
void dfnlow(int nowNode, int parentNode)
{
int childNode, i;
dfn[nowNode] = low[nowNode] = num++;
for(i = 1; i <= link_a[nowNode][0]; ++i)
{
childNode = link_a[nowNode][i];
if(dfn[childNode] < 0)
{
dfnlow(childNode, nowNode);
low[nowNode] = Min(low[nowNode], low[childNode]);
if(low[childNode] > dfn[nowNode])
insertarray(nowNode,childNode);
}
else if(childNode != parentNode)
low[nowNode] = Min(low[nowNode], dfn[childNode]);
}
}
void input()
{
int i, j, node1, node2, edgeNum;
char ch;
for(i = 0; i < nodeNum; ++i)
{
cin >> node1;
cin >> ch;
cin >> edgeNum;
cin >> ch;
for(j = 0; j < edgeNum; ++j)
{
cin >> node2;
link_a[node1][++link_a[node1][0]] = node2;
link_a[node2][++link_a[node2][0]] = node1;
}
}
}
// 소트 개선할수 있음
void sort_node()
{
int i, j, min_index, temp[2];
for(i = 0; i < ind; ++i)
{
min_index = i;
for(j = i+1; j < ind; ++j)
{
if(node[min_index][0] > node[j][0])
{
min_index = j;
}
else if(node[min_index][0] == node[j][0] && node[min_index][1] > node[j][1])
{
min_index = j;
}
}
temp[0] = node[i][0];
temp[1] = node[i][1];
node[i][0] = node[min_index][0];
node[i][1] = node[min_index][1];
node[min_index][0] = temp[0];
node[min_index][1] = temp[1];
}
}
int find_start()
{
int i;
for(i = 0; i <= nodeNum; ++i)
{
if(low[i] == -1)
break;
}
return i;
}
void process()
{
int cou = 0, i;
startNode = find_start();
while (startNode != nodeNum)
{
dfnlow(startNode, -1);
startNode = find_start();
}
sort_node();
cout << ind << " critical links" << endl;
for(i = 0; i < ind; ++i)
cout << node[i][0] << " - " << node[i][1] << endl;
cout << endl;
}
int main()
{
;
while(cin >> nodeNum)
{
init();
input();
process();
}
return 0;
}
18년 전