Cod sursa(job #1684055)

Utilizator SlevySlevoaca Stefan-Gabriel Slevy Data 10 aprilie 2016 19:08:23
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 2.18 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>

using namespace std;

ifstream in("ctc.in");
ofstream out("ctc.out");
const int NMAX = 100001;
vector<int> g[NMAX];
vector<int> gt[NMAX];
bitset<NMAX> mark;
queue<int> order;
stack<int> st;
int where[NMAX];
int n,m;
vector<int> ctcs[NMAX];

void read_data()
{
    in>>n>>m;
    int x,y;
    for(int i=1;i<=m;i++)
    {
        in>>x>>y;
        g[x].push_back(y);
        gt[y].push_back(x);
    }
    in.close();
}

void dfs(int node)
{
    mark.set(node);
    order.push(node);
    st.push(node);
    int y,target,ok;
    while(!st.empty())
    {
        y = st.top();
        ok = 0;
        for(unsigned int i=0;i<g[y].size();i++)
            if(!mark.test(g[y][i]))
        {
            target = g[y][i];
            ok = 1;
            break;
        }
        if(ok)
        {
            order.push(target);
            st.push(target);
            mark.set(target);
        }
        else
            st.pop();
    }
}

void dfs_m(int node,int ctc)
{
    st.push(node);
    int y,target,ok;
    where[node] = ctc;
    while(!st.empty())
    {
        y = st.top();
        ok = 0;
        for(unsigned int i=0;i<gt[y].size();i++)
            if(where[gt[y][i]] == -1)
        {
            target = gt[y][i];
            ok = 1;
            break;
        }
        if(ok)
        {
            st.push(target);
            where[target] = ctc;
        }
        else
            st.pop();
    }
}

int main()
{
    read_data();
    for(int i=1;i<=n;i++)
        if(!mark.test(i))
        dfs(i);
    int ctc = 0;
    for(int i=1;i<=n;i++)
        where[i] = -1;
    while(!order.empty())
    {
        if(where[order.front()] == -1)
        {
            dfs_m(order.front(),ctc);
            ctc++;
        }
        order.pop();
    }
    out<<ctc<<"\n";
    for(int i=1;i<=n;i++)
        ctcs[where[i]].push_back(i);
    for(int i=0;i<ctc;i++)
    {
        for(unsigned int j=0;j<ctcs[i].size();j++)
            out<<ctcs[i][j]<<" ";
        out<<"\n";
    }
    out.close();
    return 0;
}