Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- int visited[100010];
- vector <int> g[100010];
- int name[1000010];
- void dfs(int x)
- {
- if(visited[x])
- {
- return ;
- }
- visited[x]=true;
- for(auto c : g[x])
- {
- if(!visited[c])
- {
- dfs(c);
- }
- }
- }
- int main()
- {
- int n, m;
- cin >> n >> m;
- int u,v;
- for(int i=0; i<m; ++i)
- {
- cin >> u >> v;
- g[u].push_back(v);
- g[v].push_back(u);
- }
- int cnt=0;
- for(int i=1; i<=n; ++i)
- {
- if(!visited[i])
- {
- dfs(i);
- ++cnt;
- name[cnt]=i;
- }
- }
- int k=cnt-1;
- cout << k << "\n";
- for(int i=1; i<=k; ++i)
- {
- cout << name[i] << " " << name[i+1] << "\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement