Depth First Search

This is an algorithm that recursively explores neighbors of a vertex until all vertices are visited. The starting vertex is called the source.

How DFS works

Traversal starts on some source vertex \(u\) and marks it as visited, if a neighbor of the current vertex is not visited move to that vertex and repeat. If all neighbors of the current vertex are visited then move back to the parent vertex.

The time complexity of this traversal is \(O(N + M)\) where \(N\) is the number of vertices and \(M\) is the number of edges.

const int maxN = 200'001;

bool vis[maxN];
vector<int> adj[maxN]; // adjacency list

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

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

Path Finding

easy

Given an undirected graph \(G\) consisting of \(N\) vertices numbered \(1\) through \(N\) and \(M\) edges, check if vertex \(1\) can reach vertex \(N\) and print a possible path.

Solution

If we start a DFS traversal on vertex \(1\), we can check vis[N] to know whether or not a path exists. Our goal is to retrieve the path our traversal took to reach vertex \(N\).

To achieve this, we will store an array \(p\) where \(p_i\) is the vertex which led the DFS to discover vertex \(i\). With this we can trace the path from \(N\) back to \(1\).

const int maxN = 200'001;
int vis[maxN], p[maxN];
vector<int> adj[maxN];

void dfs (int u) {
    vis[u] = true;
    for (int v : adj[u]) {
        if (!vis[v]) {
            p[v] = u; // we discovered v through u
            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);
    }

    dfs(1);

    if (!vis[n]) cout << "No";
    else {
        cout << "Yes\n";

        vector<int> pth;
        for (int i = n ; i != 1 ; i = p[i]) { // trace back loop 
            pth.push_back(i);  
        }

        reverse(pth.begin(), pth.end());
        cout << 1 << ' '; 
        for (int i : pth) cout << i << ' ';
    }
}

Building Teams

CSES easy

There are \(N\) pupils in a class, and \(M\) friendships between them. Your task is to divide the pupils into two teams in such a way that no two pupils in a team are friends. You can freely choose the sizes of the teams.

Solution

Tip

Its a useful trick to try to visualize binary relationships as vertices and edges.

We can say that pupils are vertices and a friendship between 2 pupils connects them with an edge.

We notice that we must assign a color to each vertex (e.g either red or blue) such that the endpoints of each edge have different colors. This is known as two-coloring.

For any valid assignment, if we flip the color of each vertex from red to blue or vice versa, the assignment will remain valid, so we can assume that vertex \(1\) is always red.

From that we can observe that all its neighbors must be blue and recursively we can assign colors to all vertices.

Important

If we color a vertex some color \(C\) then find out we previously colored one of its neighbors \(C\) as well then we must terminate immediately as we have found a contradiction.

The graph may consist of several separate components so we must solve for each one individually.

const int maxN = 200'001;

bool vis[maxN], clr[maxN], contradiction = false;
vector<int> adj[maxN];

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

    for (int v : adj[u]) {
        if (vis[v]) {
            if (clr[v] == clr[u]) contradiction = true;
        } else {
            clr[v] = !clr[u];
            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);
    }

    for (int i = 1 ; i <= n ; i++) if (!vis[i]) dfs(i);

    if (contradiction) cout << "IMPOSSIBLE";
    else {
        for (int i = 1 ; i <= n ; i++) cout << 1 + clr[i] << ' ';
    }
}