Cod sursa(job #2176191)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 16 martie 2018 21:27:57
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <cstdio>
#include <vector>
#include <stack>
#define pb push_back
using namespace std;
const int nmax=100004;
vector<int>adj[nmax],adjt[nmax],sols[nmax];
int n,p,vis[nmax],vis2[nmax];
stack<int>stk;
inline void citire()
{
    int m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        adj[x].pb(y);
        adjt[y].pb(x);
    }
}
void dfs(int nod)
{
    vis[nod]=1;
    for(vector<int>::iterator it=adj[nod].begin();it!=adj[nod].end();++it)
    {
        if(!vis[*it]) dfs(*it);
    }
    stk.push(nod);
}
inline void topological()
{
    for(int i=1;i<=n;i++)
    {
        if(!vis[i]) dfs(i);
    }
}
void dfs2(int nod)
{
    sols[p].pb(nod);
    vis2[nod]=1;
    for(vector<int>::iterator it=adjt[nod].begin();it!=adjt[nod].end();++it)
    {
        if(vis2[*it]==0) dfs2(*it);
    }
}
inline void kosaraju()
{
    while(!stk.empty())
    {
        int nod=stk.top();
        stk.pop();
        if(vis2[nod]==0) ++p,dfs2(nod);
    }
}
inline void afis()
{
    printf("%d\n",p);
    for(int i=1;i<=p;i++)
    {
        for(vector<int>::iterator it=sols[i].begin();it!=sols[i].end();++it) printf("%d ",*it);
        printf("\n");
    }
}
int main()
{
    freopen ("ctc.in","r",stdin);
    freopen ("ctc.out","w",stdout);
    citire();
    topological();
    kosaraju();
    afis();
}