Connected Components

Lab C++ Advanced 30 points

Read an undirected graph and print the number of connected components and the size of the largest one, using an iterative DFS with a stack.

Input

n m, then m lines u v (nodes 1..n).

Output

Two lines.

Example

Input

Output

4
3

Sample input available Sample output available

Editor

C++

Hints

Start a new search from every node not yet seen; each search covers one component.

Solution explanation

An explicit stack avoids deep recursion on big graphs.

Show solution

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vector<bool> seen(n + 1, false);
    int components = 0, largest = 0;
    for (int start = 1; start <= n; start++) {
        if (seen[start]) continue;
        components++;
        int size = 0;
        stack<int> st;
        st.push(start);
        seen[start] = true;
        while (!st.empty()) {
            int u = st.top();
            st.pop();
            size++;
            for (int v : adj[u]) {
                if (!seen[v]) {
                    seen[v] = true;
                    st.push(v);
                }
            }
        }
        largest = max(largest, size);
    }
    cout << components << "\n" << largest << "\n";
    return 0;
}

Output

Answer