Cod sursa(job #652283)

Utilizator mihai995mihai995 mihai995 Data 23 decembrie 2011 20:02:22
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <vector>
using namespace std;

const int N=100005;
int stack[N],n,D=-1;
char PRINT[7*N];
bool use[N],okay[N];
vector<int> a1[N],a2[N],rez[N];

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

void push(int x)
{
    if (x<10)
    {
        PRINT[++D]=x+'0';
        return;
    }
    push(x/10);
    PRINT[++D]=x%10+'0';
}

void dfs(int x)
{
    okay[x]=true;
    stack[++stack[0]]=x;
    for (vector<int>::iterator i=a1[x].begin();i!=a1[x].end();i++)
        if (!okay[*i])
            dfs(*i);
}

void df(int x)
{
    use[x]=true;
    push(x);
    PRINT[++D]=' ';
    for (vector<int>::iterator i=a2[x].begin();i!=a2[x].end();i++)
        if (!use[*i])
            df(*i);
}

int main()
{
    int nr=0,x,y,m;
    in>>n>>m;
    while (m--)
    {
        in>>x>>y;
        a1[x].push_back(y);
        a2[y].push_back(x);
    }
    for (int i=1;i<=n;i++)
        if (!okay[i])
            dfs(i);
    for (int i=stack[0];i;i--)
        if (!use[stack[i]])
        {
            nr++;
            df(stack[i]);
            PRINT[++D]='\n';
        }
    out<<nr<<"\n"<<PRINT;
    return 0;
}