/*2
#include <stdio.h>
int main()
{
int age;
printf("Enter your age:");
scanf("%d",&age);
if(age>=18){
printf("you are an adult.\n");
}
else{
printf("you are not yet an adult.\n");
}
return 0;
}
#include <stdio.h>
int arr[6]={1,10,100,1000,10000,100000};
int tri_count(int n)
{
//n에 3의배수가 몇 개 들어있는지 리턴
int cnt=0;
while(n){
if(n%10!=0&&n%10%3==0)
cnt++;
n=n/10;
}
return cnt;
}
int main()
{
int n,i,m=10,p,wo=0,j,c,ans=0,a=1,s=0;
scanf("%d",&n);
for(i=1;i<=n;i++){
ans=ans+tri_count(i);
}
printf("%d",ans);
return 0;
}
그래프 ( 노드 엣지 )
노드의 연결상태 -> 인접행렬( 2차원배열)*/
/**
DFS VS BFS
Depth(깊이) Breadthwidth(너비)
First Search
재귀 or stack queue
**/
#include <stdio.h>
int n,front=-1,back=-1;
int arr[101][101]={};
int infect[101]={};
int queue[101]={};
void push(int x)
{
back++;
queue[back]=x;
}
int pop()
{
int tem;
if(front==back){
return 0;
}
else{
tem=queue[front];
front++;
return tem;
}
}
void bfs(int v)
{
int w;
push(v);
while(front!=back){
w = pop();
for(int j=1;j<=n;j++){
if(arr[w][j]==1 && infect[j]==0){
push(j);
printf("%d ",j);
infect[j]=1;
}
}
}
printf("%d",back+1);
return ;
}
void dfs(int v)
{
printf("%d->",v);
infect[v]=1;
// 노드 v와 연결되어있 && 다녀오지않은곳
for(int i=1;i<=n;i++){
if(arr[v][i]==1 && infect[i]==0){
dfs(i);
}
}
}
int main()
{
int m,i,a,b;
scanf("%d",&n);
scanf("%d",&m);
for(i=1;i<=m;i++){
scanf("%d %d",&a,&b);
arr[a][b]=1;
arr[b][a]=1;
}
//dfs(1);
bfs(1);
}