#include <cstdio>
#include <queue>
using namespace std;
bool map[501][501],chk[501];
int n, cnt=0,cnt1=0;
queue <int> q;
void BFS(int num)
{
while(!q.empty())
int s= q.size();
while(s--)
int num=q.front();
q.pop();
for(int i =1; i <=n ; i++)
if(!chk[i] && map[num][i]) {
q.push(i); cnt++; chk[i]= true;
}
if(++cnt1>1) break;
int main()
int t;
scanf("%d %d", &n, &t);
for(int i =0; i < t; i++)
int a, b;
scanf("%d %d", &a, &b);
map[a][b]= true;
q.push(1);
BFS(1);
printf("%d\n", cnt);
댓글을 작성하려면 로그인해야 합니다.
koko514 6년 전
#include <cstdio>
#include <queue>
using namespace std;
bool map[501][501],chk[501];
int n, cnt=0,cnt1=0;
queue <int> q;
void BFS(int num)
{
while(!q.empty())
{
int s= q.size();
while(s--)
{
int num=q.front();
q.pop();
for(int i =1; i <=n ; i++)
{
if(!chk[i] && map[num][i]) {
q.push(i); cnt++; chk[i]= true;
}
}
}
if(++cnt1>1) break;
}
}
int main()
{
int t;
scanf("%d %d", &n, &t);
for(int i =0; i < t; i++)
{
int a, b;
scanf("%d %d", &a, &b);
map[a][b]= true;
}
q.push(1);
BFS(1);
printf("%d\n", cnt);
}