수다닷컴

void dfs(int v)
{
node_pointer w;
visited[v] = TRUE;
printf(%5d, v);
for(w = graph[v] ; w ; w = w-link)
{
if(!visited[w-vertex])
dfs(w-vertex);
}
}void dfnlow(int u, int v) {
node_pointer ptr;
int w;
dfn[u] = low[u] = num++;
for(ptr = graph[u]; ptr; ptr = ptr-link) {
w = ptr-vertex;
if(dfn[w] 0) {
dfnlow(w, u);
low[u] = MIN(low[u], low[w]);
} else if( w != v)
low[u] = MIN(low[u], dfn[w]);
}
}void bicon(int u, int v) {
node_pointer ptr;
int w;
edge e;
dfn[u] = low[u] = num++;

for(ptr = graph[u]; ptr; ptr = ptr-link)
{
w = ptr-vertex;

if(v!=w && dfn[w] dfn[u])
{
set[top].v = u;
set[top].w = w;
++top;
if(dfn[w] 0)
{
bicon(w,u);
low[u] = MIN(low[u], low[w]);

if(low[w] = dfn[u])
{
printf(\nNew biconnected component:\n);
do
{
e = set[--top];
printf(%d,%d, e.v, e.w);
}while( !(e.v == u && e.w == w));
count++;
printf(\n);
}
} else if (w!=v)
{
low[u] = MIN(low[u], dfn[w]);
}
}
}
}

void connected()
{
int i;
for(i = 0 ; i n ; i++)
{
if(!visited[i])
dfs(i);
bicon(i,-1);
}
return ;
}

--------------------------------------------------------------------
코드상에서 New bi component를 생성할 때 count 변수를 1씩 증가시켜서
connected인지 아닌지를 판단하려다가 bi component가 생성될 때마다
count 변수를 증가시켜 판단하는 방식이 아니라는 것을 알게 됐습니다.
계속 생각해봐도 어떤 방식으로 connected인지 아닌지를 판단하는지 몰라서
답답한 마음에 이렇게 글을 올려봅니다.고수님들 좀 도와주세요!!!!!

신청하기