Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <queue>
- using namespace std;
- ifstream f("componenteconexe.in");
- ofstream of("componenteconexe.out");
- int n, viz[101], viz1[101];
- bool a[101][101];
- queue <int> coada;
- priority_queue <int, vector<int>, greater<int>> coada1;
- void dfs1(int nod) {
- //of << nod << " ";
- viz1[nod] = 1;
- for (int i = 1; i <= n; i++)
- if (a[nod][i] && !viz1[i]) dfs1(i);
- }
- void bfs(int nod) {
- viz[nod] = 1;
- coada.push(nod);
- while (!coada.empty()) {
- for (int i = 1; i <= n; i++) {
- if (a[coada.front()][i] && !viz[i])
- viz[i] = 1, coada.push(i);
- }
- coada1.push(coada.front());
- coada.pop();
- }
- }
- int main() {
- int c, b, i, cnt = 0;
- f >> n;
- if (n == 1) {
- of << 1 << endl;
- of << 1;
- return 0;
- }
- for (i = 0; i < n; i++) {
- f >> c >> b;
- a[c][b] = true;
- a[b][c] = true;
- }
- for (i = 1; i <= n; i++)
- if (!viz1[i]) cnt++, dfs1(i);
- of << cnt << endl;
- for (i = 1; i <= n; i++)
- if (!viz[i]) {
- bfs(i);
- while (!coada1.empty())
- of << coada1.top() << " ", coada1.pop();
- of << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement