Connected Components

In an undirected graph, vertices \(u\) and \(v\) are said to belong to the same connected component if there exists a path connecting them. If a graph consists of a single component, its considered connected.

Building Roads

CSES easy

There are \(n\) cities, and \(m\) roads between them. Your task is to find out the minimum number of roads to add so that there is a route between any two cities, and also determine which roads should be built.

Solution

The goal here is to add edges so the graph becomes connected. If we add an edge connecting vertices of the same component, the other components will be unaffected, and if we add an edge between vertices of different components they will merge.

If there are \(C\) components then we need to add \(C - 1\) edges. There are many ways to choose these edges, a simple way is to pick an arbitrary vertex from the first component and connect it to an arbitrary vertex from each of the remaining components.

const int maxN = 200'001;

bool vis[maxN];
vector<int> adj[maxN];

void dfs (int u) {
    vis[u] = true;

    for (int v : adj[u]) {
        if (!vis[v]) dfs(v);
    }
}

int main () { 
    int n, m;
    cin >> n >> m;

    for (int i = 0 ; i < m ; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> sources;

    for (int i = 1 ; i <= n ; i++) if (!vis[i]) {
        sources.push_back(i);
        dfs(i);
    }

    cout << sources.size() - 1 << endl;

    for (int i = 1 ; i < sources.size() ; i++) {
        cout << sources[0] << ' ' << sources[i] << endl;
    }
}

Cyclic Components

Codeforces easy

Given an undirected graph, count the number of components which are cycles. A component of \(k\) vertices \(v_1, v_2, ..., v_k\) is considered a cycle if it has exactly \(k\) edges: \((v_1, v_2), (v_2, v_3), ..., (v_k, v_1)\).

Note

If there is any order of the vertices which satisfies the above condition then its a cycle.

Solution

If a component is a cycle then all its vertices are adjacent to exactly \(2\) other vertices. In fact, this is a sufficient condition to determine if a component is a cycle.

DFS can be used to explore all vertices of a component to validate this condition.

const int maxN = 200'001;

vector<int> adj[maxN];
bool vis[maxN];
 
bool dfs (int u) {
    vis[u] = 1;
    bool ret = (adj[u].size() == 2);
 
    for (int v : adj[u]) {
        if (!vis[v]) ret &= dfs(v);
    }
 
    return ret;
}
 
int main () { 
    int n, m;
    cin >> n >> m;
 
    for (int i = 0 ; i < m ; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
 
    int ans = 0;
 
    for (int i = 1 ; i <= n ; i++) {
        if (!vis[i]) ans += dfs(i);
    }
    
    cout << ans << endl;
}