Cod sursa(job #3369734)

Utilizator Vlad_prisVlad Prismareanu Vlad_pris Data 22 octombrie 2026 02:12:24
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.97 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");

vector<vector<int>> Adj;

void read(vector<vector<int>>& Adj,int n,int m){
    int x,y;
    
    for(int i=1;i<=m;i++){
        fin>>x>>y;
        Adj[x].push_back(y);
        Adj[y].push_back(x);
    }
}
void write(const vector<vector<int>>& Adj, int n){
    for(int i=1;i<=n;i++){
        for(int neighbor : Adj[i]){
            fout<<neighbor<<" ";
        }
        fout<<"\n";
    }
}

// void convert_ML(bool adj[100][100],int n){
//     for(int i=1;i<=n;i++){
//         for(int j=1; j<=n;j++){
//             if(adj[i][j] == 1){
//                 Adj[i].push_back(j);
//                 Adj[j].push_back(i);
//                 adj[i][j]=0;
//                 adj[j][i]=0;
//             }
//         }
//     }
// }
// void convert_LM(const vector<vector<int>>& Adj, int n, bool adj[100][100]){
//     for(int i=1;i<=n;i++){
//         for(int neighbor : Adj[i]){
//             adj[i][neighbor] = 1;
//             adj[neighbor][i] = 1;
//         }
//     }
// }
// void read(bool Adj[100][100],int n,int m){
//     int x,y;
    
//     for(int i=1;i<=m;i++){
//         fin>>x>>y;
//         Adj[x][y]=1;
//         Adj[y][x]=1;
//     }
// }
// void write(bool Adj[100][100],int n){
//     for(int i=1;i<=n;i++){
//         for(int j=1;j<=n;j++){
//             fout<<Adj[i][j]<<" ";
//         }
//         fout<<"\n";
//     }
// }
void BFS(int start, const vector<vector<int>>& Adj, vector<bool>& visited) {
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        fout << node << " "; 

        for (int neighbor : Adj[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}
void DFS(int node, const vector<vector<int>>& Adj, vector<int>& visited) {

    visited[node] = 1;

    for (int neighbor : Adj[node]) {
        if (visited[neighbor] == 0) {
            visited[neighbor] = 1;
            DFS(neighbor, Adj, visited);
        }
    }
}
// vom folosi DFS pentru a determina daca graful este aciclic sau nu. 
// cand gasim un nod care este deja vizitat si este in curs de vizitare, inseamna ca am gasit un ciclu.
// Complexitatea este O(n + m), unde n este numarul de noduri si m este numarul de muchii.
bool topologicalDFS(int node, const vector<vector<int>>& Adj, vector<int>& state, vector<int>& order) {
    state[node] = 1;

    for (int neighbor : Adj[node]) {
        if (state[neighbor] == 1) {
            return false;
        }
        if (state[neighbor] == 0 && !topologicalDFS(neighbor, Adj, state, order)) {
            return false;
        }
    }

    state[node] = 2;
    order.push_back(node);
    return true;
}
// vom verifica daca graful este bipartit sau nu folosind 1 si 2 pentru a colora nodurile. 
// Daca gasim doua noduri adiacente cu aceeasi culoare, graful nu este bipartit. Parcurgerea este un DFS, 
// complexitatea este O(n + m), unde n este numarul de noduri si m este numarul de muchii.
bool bipart(int node, const vector<vector<int>>& Adj, vector<int>& color) {
    for (int neighbor : Adj[node]) {
        if (color[neighbor] == 0) {
            color[neighbor] = 3 - color[node];
            if (!bipart(neighbor, Adj, color)) {
                return false;
            }
        } else if (color[neighbor] == color[node]) {
            return false;
        }
    }
    return true;
}
int main(){
    int n,m;
    fin>>n>>m;
    Adj.resize(n + 1);
    read(Adj,n,m);
    vector<int> visited (n + 1, 0);
    // DFS(1, Adj, visited);
    int count = 0;
    for (int i = 1; i <= n; i++) {
        if (visited[i] == 0) {
            count++;
            DFS(i, Adj, visited);
        }
    }
    fout << count << "\n";
    
}