20260528
/*
// 4503 바이러스 - dfs 인접 리스트
#include <stdio.h>
#include <stdlib.h>
typedef struct GraphNode
{
int vertex;
struct GraphNode* link;
} GraphNode;
GraphNode* adj[101] = {};
int v[101] = {};
int n, k = 0;
void insertEdge(int a, int b)
{
GraphNode* node = (GraphNode*)malloc(sizeof(GraphNode));
node->vertex = b;
node->link = adj[a];
adj[a] = node;
}
void dfs(int x)
{
GraphNode* p = adj[x];
v[x] = 1;
while(p != NULL)
{
int next = p->vertex;
if(v[next] == 0)
{
k++;
dfs(next);
}
p = p->link;
}
}
int main()
{
int m, i, a, b;
scanf("%d %d", &n, &m);
for(i = 0; i < m; i++)
{
scanf("%d %d", &a, &b);
insertEdge(a, b);
insertEdge(b, a);
}
dfs(1);
printf("%d", k);
return 0;
}
*/
/*
// 4714 키 순서 - dfs 인접리스트
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
int vertex;
struct Node* link;
} Node;
Node* bigGraph[501] = {};
Node* smallGraph[501] = {};
int v[501] = {};
int n, m;
int cnt;
void insertEdge(Node* adj[], int a, int b)
{
Node* node = (Node*)malloc(sizeof(Node));
node->vertex = b;
node->link = adj[a];
adj[a] = node;
}
void dfs(Node* adj[], int x)
{
Node* p = adj[x];
while(p != NULL)
{
int next = p->vertex;
if(v[next] == 0)
{
v[next] = 1;
cnt++;
dfs(adj, next);
}
p = p->link;
}
}
void resetVisited()
{
for(int i = 1; i <= n; i++)
{
v[i] = 0;
}
}
int main()
{
int i, a, b;
int answer = 0;
scanf("%d %d", &n, &m);
for(i = 0; i < m; i++)
{
scanf("%d %d", &a, &b);
insertEdge(bigGraph, a, b);
insertEdge(smallGraph, b, a);
}
for(i = 1; i <= n; i++)
{
int total = 0;
resetVisited();
v[i] = 1;
cnt = 0;
dfs(bigGraph, i);
total += cnt;
resetVisited();
v[i] = 1;
cnt = 0;
dfs(smallGraph, i);
total += cnt;
if(total == n-1)
{
answer++;
}
}
printf("%d", answer);
return 0;
}
*/
// 4503 바이러스 - bfs 인접 리스트
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
int vertex;
struct Node* link;
} Node;