05-1. List Components(25) 그림의 기본 스트리밍
4023 단어 component
시간 제한
200 ms
메모리 제한
65536 kB
코드 길이 제한
8000 B
판정 절차
Standard
작자
CHEN, Yue
For a given undirected graph with N vertices and E edges, please list all the connected components by both DFS and BFS. Assume that all the vertices are numbered from 0 to N-1. While searching, assume that we always start from the vertex with the smallest index, and visit its adjacent vertices in ascending order of their indices.
Input Specification:
Each input file contains one test case. For each case, the first line gives two integers N (0
For each test case, print in each line a connected component in the format "{ v1 v2 ... vk }". First print the result obtained by DFS, then by BFS.
Sample Input:
8 6
0 7
0 1
2 0
4 1
2 4
3 5
Sample Output:
{ 0 1 4 2 7 }
{ 3 5 }
{ 6 }
{ 0 1 2 7 4 }
{ 3 5 }
{ 6 }
제출 번호
#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
#define lson rt<<1,l,MID
#define rson rt<<1|1,MID+1,r
//#define lson root<<1
//#define rson root<<1|1
#define MID ((l+r)>>1)
typedef long long ll;
typedef pair<int,int> P;
const int maxn=100;
const int base=1000;
const int inf=999999;
const double eps=1e-5;
vector<int> G[maxn];
int n;
bool vist[maxn];//dfs񈬀
bool vis[maxn];//bfs񈬀
void dfs(int s)
{
if(!vist[s])
{
vist[s]=true;
printf("%d ",s);
sort(G[s].begin(),G[s].end());
for(int i=0; i<G[s].size(); i++)
{
if(!vist[G[s][i]])dfs(G[s][i]);
}
}
}
void bfs(int s)
{
queue<int> q;
q.push(s);
while(!q.empty())
{
int k=q.front();
q.pop();
if(!vis[k])
{
vis[k]=true;
printf("%d ",k);
}
else
continue;
sort(G[k].begin(),G[k].end());
for(int i=0; i<G[k].size(); i++)
q.push(G[k][i]);
}
}
int main()
{
int m,i,j,k,t;
cin>>n>>m;
while(m--)
{
int s,e;
cin>>s>>e;
G[s].push_back(e);
G[e].push_back(s);
}
for(i=0; i<n; i++)
{
if(!vist[i])
{
printf("{ ");
dfs(i);
printf("}
");
}
}
// printf("------------------
");
for(i=0; i<n; i++)
{
if(!vis[i])
{
printf("{ ");
bfs(i);
printf("}
");
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Angular의 DI는 구성 요소를 더 스마트하게 만들 수 있습니다.Angular에 내장된 종속성 주입은 매우 강력하며 오늘 우리는 이를 사용하여 구성 요소를 스마트하게 만드는 방법을 살펴보겠습니다. 버튼 구성요소에 대해 알아보겠습니다. 여기에서 버튼 구성 요소가 다양한 구성 옵션을...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.