Cod sursa(job #1047033)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 3 decembrie 2013 20:33:13
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
//Ŕ#include <iostream>
#include <fstream>
using namespace std;

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

#include <vector>
#define pb push_back
#define LE 100666
#define cout g

vector<int> H[LE],result[LE];
int i,k,nrc,st[LE];
bool fr_up[LE],viz[LE];
int n,m;

void dfs(int nod)
{
    viz[nod]=true;
    st[++k]=nod;
    fr_up[nod]=true;
//    cout<<nod<<'\n';
    int posk=k,i,N=H[nod].size();
    bool okz=false;
    //if (nod==6)
     // int te=0;

    for(i=0; i<N; ++i)
        if (viz[H[nod][i]]==false)
          dfs(H[nod][i]);

    for(i=posk; i<=k; ++i) fr_up[st[i]]=false;

    for(i=posk; i<=k; ++i)
    {
        int N2=H[st[i]].size(),j;
        for(j=0; j<N2; ++j)
          if (fr_up[H[st[i]][j]])
          {
            okz=true;
            break;
          }
    }

    if (okz==false)
    {
        for(i=posk,++nrc; i<=k; ++i) result[nrc].pb(st[i]);
        k=posk-1;
    }
    else
        for(i=posk; i<=k; ++i) fr_up[st[i]]=true;
}

int main()
{
    f>>n>>m;
    for(i=1; i<=m; ++i)
    {
        int xx,yy;
        f>>xx>>yy;
        H[xx].pb(yy);
    }

    for(i=1; i<=n; ++i)
        if (viz[i]==false)
        {
            k=0;
            dfs(i);
        }

    cout<<nrc<<'\n';

    for(i=1; i<=nrc; ++i,cout<<'\n')
    {
        int N=result[i].size();
        //cout<<N<<" ";
        for(int j=0; j<N; ++j) cout<<result[i][j]<<" ";
    }


    f.close();
    g.close();
    return 0;
}