<div> <div>=== C++ 코드 ===</div> <div><br></div> <div>#include <cstdio></div> <div>#include <vector></div> <div>#include <algorithm></div> <div>#include <stack></div> <div>#include <utility></div> <div><br></div> <div>using namespace std;</div> <div><br></div> <div>vector<vector<int> > adj;</div> <div>vector<int> discovered,parent;</div> <div>vector<pair<int,int> > cutline;</div> <div>int v,e;</div> <div>stack<int> Stack;</div> <div>int counter;</div> <div><br></div> <div>int dfs(int here)</div> <div>{</div> <div> discovered[here]=counter++;</div> <div> int ret = discovered[here]; // 현재위치에서 역방향으로 갈 수 있는 순서번호.</div> <div><br></div> <div> for(int i=0;i<adj[here].size();i++)</div> <div><span style="white-space:pre;"> </span>{</div> <div> int next = adj[here][i];</div> <div> if(next==parent[here]) </div> <div><span style="white-space:pre;"> </span>continue;</div> <div><br></div> <div> if(discovered[next]==-1)</div> <div><span style="white-space:pre;"> </span>{</div> <div> parent[next] = here;</div> <div> int sub = dfs(next); // 다음 subtree에서 역방향 최소값.</div> <div> ret = min(sub,ret);</div> <div> }</div> <div><span style="white-space:pre;"> </span>else</div> <div><span style="white-space:pre;"> </span>{</div> <div> ret = min(ret, discovered[next]); // 최소값 갱신.</div> <div> }</div> <div> }</div> <div><br></div> <div> // 올라갈 방법이 없음.</div> <div> if(ret==discovered[here])</div> <div><span style="white-space:pre;"> </span>{</div> <div> int a = min(here,parent[here]);</div> <div> int b = max(here,parent[here]);</div> <div> if(a!=-1) // root가 아닐 때.</div> <div> cutline.push_back(make_pair(a,b));</div> <div> }</div> <div><br></div> <div> return ret;</div> <div>}</div> <div><br></div> <div>void dfsAll()</div> <div>{</div> <div> parent = discovered = vector<int>(v+1,-1);</div> <div> for(int i=1;i<=v;i++)</div> <div><span style="white-space:pre;"> </span>{</div> <div> if(discovered[i]==-1)</div> <div><span style="white-space:pre;"> </span>{</div> <div> dfs(i);</div> <div> }</div> <div> }</div> <div>}</div> <div><br></div> <div>int main()</div> <div>{</div> <div><span style="white-space:pre;"> </span>int j=0;</div> <div><br></div> <div><span style="white-space:pre;"> </span>printf("정점 갯수와 간선 개수를 입력하세요 : ");</div> <div> scanf("%d %d",&v,&e);</div> <div><br></div> <div> adj.resize(v+1);</div> <div><br></div> <div> int a,b;</div> <div> while(e--)</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>printf("간선의 양 끝점을 입력하세요 : ");</div> <div> scanf("%d %d",&a,&b);</div> <div><br></div> <div> adj[a].push_back(b);</div> <div> adj[b].push_back(a);</div> <div> }</div> <div><br></div> <div> dfsAll();</div> <div> sort(cutline.begin(),cutline.end());</div> <div><br></div> <div> printf("단절선의 갯수는 %d 입니다.\n", cutline.size());</div> <div> for(int i=0; i<cutline.size(); i++)</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>j=i+1;</div> <div> printf(" %d 번째 단절선 (%d, %d)\n", j, cutline[i].first, cutline[i].second);</div> <div> }</div> <div><br></div> <div><span style="white-space:pre;"> </span>while(e--)</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>int c, d;</div> <div><span style="white-space:pre;"> </span>int i=0;</div> <div><span style="white-space:pre;"> </span>printf("단절선 판별을 위해 간선의 양 끝점을 입력하세요. : ");</div> <div><span style="white-space:pre;"> </span>scanf("%d %d", &c, &d);</div> <div><span style="white-space:pre;"> </span></div> <div><span style="white-space:pre;"> </span>if(c==-1 && d==-1)</div> <div><span style="white-space:pre;"> </span>break;</div> <div><span style="white-space:pre;"> </span></div> <div><span style="white-space:pre;"> </span>if(cutline[i].first==c && cutline[i].second==d)</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>printf("(%d %d)는 단절선 입니다.\n", c, d);</div> <div><span style="white-space:pre;"> </span>i++;</div> <div><span style="white-space:pre;"> </span>}</div> <div><span style="white-space:pre;"> </span>else</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>printf("(%d %d)는 단절선이 아닙니다.\n", c, d);</div> <div><span style="white-space:pre;"> </span>i++;</div> <div><span style="white-space:pre;"> </span>}</div> <div><br></div> <div><span style="white-space:pre;"> </span>printf("종료 하려면 -1, -1 입력\n");</div> <div><span style="white-space:pre;"> </span>}</div> <div><br></div> <div> return 0;</div> <div>}</div></div> <div><br></div> <div><br></div> <div><span style="font-size:9pt;">-------------------------------------------------------------------------------</span></div> <div><span style="font-size:9pt;">== C 코드 ==</span></div> <div><span style="font-size:9pt;"><br></span></div> <div><span style="font-size:9pt;"><br></span></div> <div>#include <stdio.h></div> <div><br></div> <div>#define MAXV 100010</div> <div>#define MAXBUF 1000</div> <div><br></div> <div>typedef struct pair</div> <div>{</div> <div> int first, second;</div> <div>} pair;</div> <div><br></div> <div>pair make_pair(int f, int s);</div> <div><br></div> <div>typedef struct vector</div> <div>{</div> <div> int size;</div> <div> int buf[MAXBUF];</div> <div>} vector;</div> <div><br></div> <div>int v, e, counter, discovered[MAXV];</div> <div>vector adj[MAXV], parent[MAXV]];</div> <div>pair cutline[MAXBUF];</div> <div>int cutline_size = 0;</div> <div><br></div> <div>//void cutline_push_back(pair p);</div> <div>//void sort();</div> <div>//int min(int a, int b);</div> <div>//int max(int a, int b);</div> <div><br></div> <div>int dfs(int here)</div> <div>{</div> <div> discovered[here]=counter++;</div> <div> int ret = discovered[here]; // 현재위치에서 역방향으로 갈 수 있는 순서번호.</div> <div><br></div> <div> for(int i=0;i<adj[here].size;i++)</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>int next = adj[here].buf[i];</div> <div><span style="white-space:pre;"> </span>if(next == parent[here].buf[i]) </div> <div><span style="white-space:pre;"> </span>continue;</div> <div><br></div> <div> if(discovered[next]==-1)</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>parent[next].buf[i] = here;</div> <div> int sub = dfs(next); // 다음 subtree에서 역방향 최소값.</div> <div> ret = min(sub,ret);</div> <div> }</div> <div><span style="white-space:pre;"> </span>else</div> <div><span style="white-space:pre;"> </span>{</div> <div> ret = min(ret, discovered[next]); // 최소값 갱신.</div> <div> }</div> <div> }</div> <div><br></div> <div> // 올라갈 방법이 없음.</div> <div> if(ret==discovered[here])</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>int a = min(here,parent[here].buf[i]);</div> <div><span style="white-space:pre;"> </span>int b = max(here,parent[here].buf[i]);</div> <div> if(a!=-1) // root가 아닐 때.</div> <div> cutline_push_back(make_pair(a,b));</div> <div> }</div> <div><br></div> <div> return ret;</div> <div>}</div> <div><br></div> <div>void dfsAll()</div> <div>{</div> <div> parent = discovered = vector(v+1,-1); //아 여기 모르겠다 진짜</div> <div> for(int i=1;i<=v;i++)</div> <div><span style="white-space:pre;"> </span>{</div> <div> if(discovered[i]==-1)</div> <div><span style="white-space:pre;"> </span>{</div> <div> dfs(i);</div> <div> }</div> <div> }</div> <div>}</div> <div><br></div> <div>pair make_pair(int f, int s)</div> <div>{</div> <div> pair p;</div> <div> p.first = f;</div> <div> p.second = s;</div> <div> return p;</div> <div>}</div> <div><br></div> <div>void v_push_back(vector* v, int val)</div> <div>{</div> <div> v->buf[v->size] = val;</div> <div> ++v->size;</div> <div>}</div> <div><br></div> <div>void cutline_push_back(pair p)</div> <div>{</div> <div> cutline[cutline_size] = p;</div> <div> ++cutline_size;</div> <div>}</div> <div><br></div> <div>void sort()</div> <div>{</div> <div> pair tmp;</div> <div> for (int a = 0; a < cutline_size - 1; ++a)</div> <div> for (int b = a + 1; b < cutline_size; ++b)</div> <div> if (pair_cmp(&cutline[a], &cutline[b]) < 0)</div> <div> {</div> <div> tmp = cutline[a];</div> <div> cutline[a] = cutline[b];</div> <div> cutline[b] = tmp;</div> <div> }</div> <div>}</div> <div><br></div> <div>int pair_cmp(pair* a, pair* b)</div> <div>{</div> <div> if (a->first < b->first) return -1;</div> <div> if (a->first > b->first) return 1;</div> <div> </div> <div> if (a->second < b->second) return -1;</div> <div> if (a->second > b->second) return 1;</div> <div> </div> <div> return 0;</div> <div>}</div> <div><br></div> <div>int max(int a, int b)</div> <div>{</div> <div> return a > b ? a : b;</div> <div>}</div> <div><br></div> <div>int min(int a, int b)</div> <div>{</div> <div> return a < b ? a : b;</div> <div>}</div> <div><br></div> <div>int main()</div> <div>{</div> <div><span style="white-space:pre;"> </span>int j=0;</div> <div><br></div> <div><span style="white-space:pre;"> </span>printf("정점 갯수와 간선 개수를 입력하세요 : ");</div> <div> scanf("%d %d",&v,&e);</div> <div><br></div> <div> //adj.resize(v+1);</div> <div><br></div> <div> int a,b;</div> <div> while(e--)</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>printf("간선의 양 끝점을 입력하세요 : ");</div> <div> scanf("%d %d",&a,&b);</div> <div><br></div> <div><span style="white-space:pre;"> </span>v_push_back(&adj[a], b);</div> <div><span style="white-space:pre;"> </span>v_push_back(&adj[a], a);</div> <div> //adj[a].push_back(b);</div> <div> //adj[b].push_back(a);</div> <div> }</div> <div><br></div> <div> dfsAll();</div> <div> //sort(cutline.begin(),cutline.end());</div> <div><span style="white-space:pre;"> </span>sort();</div> <div><br></div> <div> printf("단절선의 갯수는 %d 입니다.\n", cutline_size);</div> <div> for(int i=0; i<cutline_size; i++)</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>j=i+1;</div> <div> printf(" %d 번째 단절선 (%d, %d)\n", j, cutline[i].first, cutline[i].second);</div> <div> }</div> <div><br></div> <div><span style="white-space:pre;"> </span>while(e--)</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>int c, d;</div> <div><span style="white-space:pre;"> </span>int i=0;</div> <div><span style="white-space:pre;"> </span>printf("단절선 판별을 위해 간선의 양 끝점을 입력하세요. : ");</div> <div><span style="white-space:pre;"> </span>scanf("%d %d", &c, &d);</div> <div><span style="white-space:pre;"> </span></div> <div><span style="white-space:pre;"> </span>if(c==-1 && d==-1)</div> <div><span style="white-space:pre;"> </span>break;</div> <div><span style="white-space:pre;"> </span></div> <div><span style="white-space:pre;"> </span>if(cutline[i].first==c && cutline[i].second==d)</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>printf("(%d %d)는 단절선 입니다.\n", c, d);</div> <div><span style="white-space:pre;"> </span>i++;</div> <div><span style="white-space:pre;"> </span>}</div> <div><span style="white-space:pre;"> </span>else</div> <div><span style="white-space:pre;"> </span>{</div> <div><span style="white-space:pre;"> </span>printf("(%d %d)는 단절선이 아닙니다.\n", c, d);</div> <div><span style="white-space:pre;"> </span>i++;</div> <div><span style="white-space:pre;"> </span>}</div> <div><br></div> <div><span style="white-space:pre;"> </span>printf("종료 하려면 -1, -1 입력\n");</div> <div><span style="white-space:pre;"> </span>}</div> <div><br></div> <div> return 0;</div> <div>}</div> <div><br></div> <div>없는 지식 쥐어짜서 해봤는데 오류가 나서 돌아가지 않네요 ㅠㅠ</div> <div><br></div> <div>도와주실 수 있으신가요?</div>