Cod sursa(job #3369732)

Utilizator Vlad_prisVlad Prismareanu Vlad_pris Data 22 octombrie 2026 02:06:22
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.66 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("graf.in");
ofstream fout("graf.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++){
        cin>>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) {

    if(visited[node] == 1) {
        return;
    }
    visited[node] = 1;

    for (int neighbor : Adj[node]) {
        if (visited[neighbor] == 0) {
            visited[neighbor] = 2;
            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";
    // for (int i = 0; i < m; i++) {
    //     int from, to;
    //     cin >> from >> to;
    //     Adj[from].push_back(to);
    // }

    // vector<int> state(n + 1, 0);
    // vector<int> order;
    // bool acyclic = true;
    // for (int node = 1; node <= n && acyclic; node++) {
    //     if (state[node] == 0) {
    //         acyclic = topologicalDFS(node, Adj, state, order);
    //     }
    // }
    // if (!acyclic) {
    //     cout << "IMPOSSIBLE\n";
    // } 
    // else {
    //     for (auto it = order.rbegin(); it != order.rend(); ++it) {
    //         cout << *it << " ";
    //     }
    //     cout << '\n';
    // }
}