Cod sursa(job #2118454)

Utilizator serjiuuAvacaritei Sergiu serjiuu Data 30 ianuarie 2018 17:54:13
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <fstream>
#include <list>
#include <bitset>
#include <stack>
#include <vector>

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

const int nmax=100005, white=0, gray=1, black=2;
int n, m;
int colour[nmax];

list <int> g[nmax], gt[nmax];
stack <int> s;
vector <int> sol[nmax];
bitset <nmax> vis;

void read_data()
{
    int i, x, y;

    fin>>n>>m;

    for(i=1;i<=m;i++)
    {
        fin>>x>>y;

        g[x].push_back(y);
        gt[y].push_back(x);
    }
}
inline void dfs(int node)
{
    list <int> :: iterator it;

    colour[node]=gray;

    for(it=g[node].begin();it!=g[node].end();it++)
        if(colour[*it]==white)
            dfs(*it);

    s.push(node);
    colour[node]=black;
}
inline void DFS(int node, int k)
{
    list <int> :: iterator it;

    vis[node]=true;
    colour[node]=white;

    for(it=gt[node].begin();it!=gt[node].end();it++)
        if(colour[*it]==black)
            DFS(*it,k);

    sol[k].push_back(node);
}
void solve()
{
    int i, k=0, node;

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

            while(!s.empty())
            {
                node=s.top();
                s.pop();

                if(!vis[node])
                {
                    k++;
                    DFS(node,k);
                }
            }
        }

    fout<<k<<'\n';

    vector <int> :: iterator it;

    for(i=1;i<=k;i++)
    {
        for(it=sol[i].begin();it!=sol[i].end();it++)
            fout<<*it<<' ';
        fout<<'\n';
    }
}
int main()
{
    read_data();
    solve();
}