UVA - 796 Critical Links문제 질문입니다.^^;;

  • @,.@
    @,.@

    문제링크 : 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; }
    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    17년 전
5개의 댓글이 있습니다.
  • astein
    astein

    WA받은 소스코드가 있으면 좀 더 쉽게 디버깅을 할 수 있을거 같네요 ^^;;;


    17년 전 link
  • admin
    admin

    소스코드와 문제 링크를 첨부 해주신다면 @_@ 좀 더 많은 분들이 해결 해 주시기 좋을꺼 같습니다.


    17년 전 link
  • JongMan
    JongMan

    오.. cut edge 문제로군요. 이거랑 관련해서는 운좋게도 [...] 이미 비슷한 문제에 대한 튜토리얼이 올라와 있습니다.
    (몇개 있지도 않은 튜토리얼 중에 잘도 .. -_-;)
    http://algospot.com/zbxe/openlecture/324
    를 참조하세요. ^^


    17년 전 link
  • @,.@
    @,.@

    풀었습니다. 감사합니다..^^;;.


    17년 전 link
  • JongMan
    JongMan

    대신 이 사이트에 자주 오셔서 질문도 많이 하시고 답변도 많이 하시고 키워도 많이 해주셔야 합니다. ㅡ,.ㅡ
    인생에 공짜는 없어요 ㅋㅋㅋㅋㅋㅋㅋㅋㅋ


    17년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.