Cod sursa(job #1645583)

Utilizator superstar1998Moldoveanu Vlad superstar1998 Data 10 martie 2016 12:56:31
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <bitset>
//define files
#define INFILE "ctc.in"
#define OUTFILE "ctc.out"
#define pb push_back
#define mp make_pair
using namespace std;
ifstream f(INFILE);
ofstream g(OUTFILE);
vector<int> G[100001],GT[100001],sol[100001],ord,use;
int n,m,ct;
void DF1(int i)
{
    use[i]=1;
    for(vector<int>::iterator it=G[i].begin();it!=G[i].end();it++)
        if(!use[*it])DF1(*it);
    ord.push_back(i);
}
void DF2(int i, int place)
{
    use[i]=place;
    for(vector<int>::iterator it=GT[i].begin();it!=GT[i].end();it++)
        if(!use[*it])DF2(*it,place);

}
int main()
{
    int x,y;
    f>>n>>m;
    for(;m;m--)
    {
        f>>x>>y;
        G[x].pb(y);
        GT[y].pb(x);
    }
    use.resize(n+1);
    for(int i=1;i<=n;i++)
        if(!use[i])DF1(i);
    use.assign(n+1,0);
    for(int i=n-1;i>=0;i--)
        if(!use[ord[i]])DF2(ord[i],++ct);
    for(int i=1;i<=n;i++)
        sol[use[i]].pb(i);
    g<<ct<<'\n';
    for(int i=1;i<=ct;i++,g<<'\n')
        for(vector<int>::iterator it=sol[i].begin();it!=sol[i].end();it++)
            g<<*it<<" ";
    f.close();
    g.close();
    return 0;
}