/* 問題文 

	有効グラフですべての頂点への道を持つ頂点があるかどうかを調べるプログラムを作成せよ
    以下のソースコードを元にして作成すること
    
   ヒント
   
   　まず、グラフを強連結成分に分割する．この結果としてDAGが得られる．DAGの頂点のうち
   　そこへ向かう辺が1本も無い頂点を考える．このような頂点が複数あれば、そのグラフに
   　すべての頂点への道を持つ頂点は無い．一つだけあればそれが求める答である．この頂点
   　に対応する元のグラフの頂点(その強連結成分に属する頂点)からは、すべての頂点への道
   　がある．
*/


#include <stdio.h>
#include <stdlib.h>
#define N 6

struct edgecell {
    int destination; /* 頂点番号 */
    struct edgecell *next; /* 次の要素を指すポインタ */
};

struct node {
    struct edgecell *adjlist; 
    int seq;
};

struct node vertex[N+1];
int counter = 0, sp = 0, stack[N+1];
int scomponent[N+1][N+1] 
int scomponent_index; 

void strongcomponent(void);

void insertNode(struct node *cell, int dest) {
    struct edgecell *next = cell->adjlist;
    if (next == NULL) {
	cell->adjlist = malloc(sizeof(struct edgecell));
	cell->adjlist->destination = dest;
	cell->adjlist->next = NULL;
    } else {
	while (next->next != NULL) {
	    next = next->next;
	}
	next->next = malloc(sizeof(struct edgecell));
	next->next->destination = dest;
	next->next->next = NULL;
    }
}

int main(void) {
    int i;
    insertNode(&vertex[1], 2);
    insertNode(&vertex[2], 1);
    insertNode(&vertex[2], 6);
    insertNode(&vertex[3], 1);
    insertNode(&vertex[3], 4);
    insertNode(&vertex[4], 2);
    insertNode(&vertex[4], 5);
    insertNode(&vertex[4], 6);
    insertNode(&vertex[5], 3);

#ifdef NDEBUG
    for (i = 1; i <= N; i++) {
	struct edgecell *next = vertex[i].adjlist;
	printf("%d: ", i);

	/* リストの末尾の要素を探す */
	while (next != NULL) {
	    printf("%d ", next->destination);
	    next = next->next;
	}
	printf("\n");
    }
    printf("\n");
#endif

    strongcomponent();

    for (i = 0; i < scomponent_index; i++) {
	int j = 0;
	while (scomponent[i][j] != 0) {
	    printf("%d,", scomponent[i][j]);
	    j++;
	}
	printf("\n");
    }
}

int visit(int v) {
    int min, m, x;
    counter++; 
    vertex[v].seq = counter; 
    min = counter; stack[++sp] = v;
    struct edgecell *p = vertex[v].adjlist;
    while (p != NULL) {
	if (vertex[p->destination].seq == 0)
	    m = visit(p->destination);
	else
	    m = vertex[p->destination].seq;
	if (m < min) min = m;
	p = p->next;
    }
    if (min == vertex[v].seq) {
	int i = 0;
	do {
	    x = stack[sp--];
	    scomponent[scomponent_index][i++] = x;
	    vertex[x].seq = N + 1;
	} while (x != v);
	scomponent_index++;
    }
    return min;
}

void strongcomponent(void) {
    int i;
    for (i = 1; i <= N; i++)
	vertex[i].seq = 0;
	
	/* すべての頂点を開始頂点として探索し始める */
    for (i = 1; i <= N; i++)
	if (vertex[i].seq == 0)  /* vertex[i].seqが0ならば、訪問済みでない(非連結グラフ対策) */
	    visit(i);
}