Cod sursa(job #1174372)

Utilizator lorundlorund lorund Data 22 aprilie 2014 17:23:39
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include <cstdio>
#include <vector>
#include <bitset>
using namespace std;

int N, M, sol;
vector<int> graph[100005], tgraph[100005];
vector<int> tsorted;
bitset<100005> visited;
vector<int> components[100005];

void bfs(int node);
void dfs(int node);
void tsort();
void tconex();

int main()
{
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);

    scanf("%d %d", &N, &M);
    for (int i=0; i<M; ++i){
        int from, to;
        scanf("%d %d", &from, &to);
        graph[from].push_back(to);
        tgraph[to].push_back(from);
    }

    tsort();
    tconex();

    printf("%d\n", sol);
    for (int i=0; i<sol; ++i){
        for (unsigned j=0; j<components[i].size(); ++j)
            printf("%d ", components[i][j]);
        puts("");
    }
    return 0;
}

void bfs(int node){
    components[sol].push_back(node);

    for (unsigned i=0; i<components[sol].size(); ++i){
        for (unsigned j=0; j<graph[components[sol][i]].size(); ++j){
            if (visited[graph[components[sol][i]][j]]){
                visited[graph[components[sol][i]][j]] = 0;
                components[sol].push_back(graph[components[sol][i]][j]);
            }
        }
    }
}

void dfs(int node){
    for (unsigned i=0; i<tgraph[node].size(); ++i){
        if (!visited[tgraph[node][i]]){
            visited[tgraph[node][i]] = 1;
            dfs(tgraph[node][i]);
        }
    }
    tsorted.push_back(node);
}

void tsort(){
    for (int i=1;i<=N; ++i){
        if (!visited[i]){
            visited[i] = 1;
            dfs(i);
        }
    }
}

void tconex(){
    for (int i=tsorted.size()-1; i>=0; --i){
        if (visited[tsorted[i]]){
            visited[tsorted[i]] = 0;
            bfs(tsorted[i]);
            ++sol;
        }
    }
}