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