Cod sursa(job #1790390)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 28 octombrie 2016 10:12:42
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <cstdio>
#include <vector>
#define NMAX 100023
#define pb push_back
using namespace std;
int n,m;
vector<int>adj[NMAX],adjt[NMAX],sol[NMAX],stk;
int solcur;
bool vis[NMAX];
inline void citire()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        adj[a].pb(b);
        adjt[b].pb(a);
    }
}
void dfs1(int nod)
{
    vis[nod]=1;
    for(vector<int>::iterator it=adj[nod].begin();it!=adj[nod].end();++it)
    {
        if(!vis[*it]) dfs1(*it);
    }
    stk.pb(nod);
}
inline void topological()
{
    for(int i=1;i<=n;i++) if(!vis[i]) dfs1(i);
}
void dfs2(int nod)
{
    vis[nod]=1;
    sol[solcur].pb(nod);
    for(vector<int>::iterator it=adjt[nod].begin();it!=adjt[nod].end();++it)
    {
        if(!vis[*it]) dfs2(*it);
    }
}
inline void kosaraju()
{
    for(int i=1;i<=n;i++) vis[i]=0;
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            dfs2(i);
            ++solcur;
        }
    }
}
inline void afisare()
{
    printf("%d\n",solcur);
    for(int i=0;i<solcur;i++)
    {
        for(vector<int>::iterator it=sol[i].begin();it!=sol[i].end();++it) printf("%d ",*it);
        printf("\n");
    }
}
int main()
{
    freopen ("ctc.in","r",stdin);
    freopen ("ctc.out","w",stdout);
    citire();
    topological();
    kosaraju();
    afisare();
}