Cod sursa(job #2309648)

Utilizator HaesteinnSabau Florin Vlad Haesteinn Data 29 decembrie 2018 15:30:16
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <bits/stdc++.h>

using namespace std;

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

vector<int> adj[50002];
vector<int> adjt[50002];
int n,m;
vector<int> sortat;
int visited[50002];
vector<vector<int> >comp;

void dfs(int v)
{
    visited[v]=1;
    for(int i=0;i<adj[v].size();i++)
    {
        int u=adj[v][i];
        if(visited[u]==0)
        {
            dfs(u);
        }
    }
    sortat.push_back(v);
}

void dfst(int v,int c)
{
    visited[v]=c;
//    cout<<v<<" ";
    for(int i=0;i<adjt[v].size();i++)
    {
        int u=adjt[v][i];
        if(visited[u]==0)
        {
            dfst(u,c);
        }
    }
    comp[c-1].push_back(v);
}

int main()
{
    fin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int v1,v2;
        fin>>v1>>v2;
        adj[v1].push_back(v2);
        adjt[v2].push_back(v1);
    }
    for(int i=1;i<=n;i++)
        if(visited[i]==0)
            dfs(i);
    memset(visited,0,sizeof(int)*(n+1));
    int c=1;
    for(int i=n-1; i>=0 ; i--)
    {
        if(visited[sortat[i]]==0)
        {
            vector<int> tmp;
            comp.push_back(tmp);
            dfst(sortat[i],c);
            c++;
        }
    }
    fout<<comp.size()<<'\n';
    for(int i=0;i<comp.size();i++)
    {
        for(int j=0;j<comp[i].size();j++)
            fout<<comp[i][j]<<' ';
        fout<<'\n';
    }
    return 0;
}