Cod sursa(job #1850793)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 18 ianuarie 2017 22:07:58
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <bitset>
#include <unordered_map>
using namespace std;

#define NMAX 100001

bitset<NMAX>visited;

vector<int>graph[NMAX], grapht[NMAX];

int n,m;

stack<int>vstack;

unordered_map<int,vector<int> >components;
vector<int> roots;

void read()
{
    scanf("%d %d ",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d %d ",&x,&y);
        graph[x].push_back(y);
        grapht[y].push_back(x);
    }
}

void dfs(int node)
{
    visited[node]=1;
    for(vector<int>::iterator it = graph[node].begin(); it!= graph[node].end(); ++it)
    {
        if(!visited[*it])
            dfs(*it);
    }
    vstack.push(node);
}

void dfs1(int u,int root)
{
    components[root].push_back(u);
    visited[u]=1;
    for(vector<int>::iterator it = grapht[u].begin(); it!= grapht[u].end(); ++it)
    {
        if(!visited[*it])
            dfs1(*it,root);
    }
}

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

    read();

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

    visited.reset();

    while(!vstack.empty())
    {
        int node = vstack.top();

        if(!visited[node])
        {
            visited[node]=1;
            roots.push_back(node);
            dfs1(node,node);
        }

        vstack.pop();
    }

    int number = components.size();
    printf("%d\n",number);

    for(int i=1;i<=number;i++)
    {
        int root = roots[i-1];
        int number1 = components[root].size();
        for(int j=0;j<number1;j++)
            printf("%d ",components[root][j]);
        printf("\n");
    }
    return 0;
}