Cod sursa(job #1776372)

Utilizator NicuBaciuNicu Baciu NicuBaciu Data 11 octombrie 2016 11:01:36
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.54 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

struct nod
{
    int viz=0;

    vector <int> v;
    vector <int> iv;
};

int n, m;

nod g[100001];
int comp[100001];
vector <int> a[100001];
int nc, k;

void dfs(int x)
{
    g[x].viz=1;
    for(int i=0; i<g[x].v.size(); i++)
        if(g[g[x].v[i]].viz==0)
            dfs(g[x].v[i]);

    comp[++nc]=x;
}

void idfs(int x)
{
    g[x].viz=-1;
    a[k].push_back(x);
    for(int i=0; i<g[x].iv.size(); i++)
        if(g[g[x].iv[i]].viz==1)
            idfs(g[x].iv[i]);
}

int main()
{
    fin >> n >> m;

    for(int i=1; i<=m; i++)
    {
        int x, y;

        fin >> x >> y;

        g[x].v.push_back(y);
        g[y].iv.push_back(x);
    }

    for(int i=1; i<=n; i++)
    {
        if(g[i].viz==0)
            dfs(i);
    }

    for(int i=n; i>=1; i--)
    {
        if(g[comp[i]].viz==1)
        {
            k++;
            idfs(comp[i]);
        }
    }

    fout << k << '\n';

    for(int i=1; i<=k; i++)
    {
        for(int j=0; j<a[i].size(); j++)
            fout << a[i][j] << " ";

        fout << '\n';
    }

    return 0;
}


//#include <fstream>
//#include <vector>
//
//using namespace std;
//
//ifstream f("ctc.in");
//ofstream g("ctc.out");
//
//int n, m, i, K, x, y, j;
//vector <int> ls[100005], lsR[100005];
//vector <int> sol[100005];
//int viz[100005], care[100005], nc;
//
//void df_inainte(int x)
//{
//    int i;
//    viz[x] = 1;
//    for (i = 0; i < ls[x].size(); i++)
//        if (viz[ ls[x][i] ] == 0)
//            df_inainte( ls[x][i] );
//    care[++nc] = x;
//}
//
//void df_inapoi(int x)
//{
//    int i;
//    viz[x] = -1;
//    sol[K].push_back(x);
//    for (i = 0; i < lsR[x].size(); i++)
//        if (viz[ lsR[x][i] ] == 1)
//            df_inapoi( lsR[x][i] );
//}
//
//int main()
//{
//    f >> n >> m;
//    while (m)
//    {
//        f >> x >> y;
//        ls[x].push_back(y);
//        lsR[y].push_back(x);
//        m--;
//    }
//
//    for (i = 1; i <= n; i++)
//        if (viz[i] == 0)
//            df_inainte(i);
//
//    for (i = n; i >= 1; i--)
//        if (viz[care[i]] != -1)
//        {
//            K++;
//            df_inapoi(care[i]);
//        }
//
//    g << K << '\n';
//    for (i = 1; i <= K; i++)
//    {
//        for (j = 0; j < sol[i].size(); j++)
//            g << sol[i][j] << ' ';
//        g << '\n';
//    }
//    return 0;
//}