Cod sursa(job #2103387)

Utilizator AlexVulpoiuAlexandru Vulpoiu AlexVulpoiu Data 10 ianuarie 2018 09:48:26
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <cstdio>
#include <vector>
using namespace std;
vector <int> a,b,g[100001],gt[100001],comp[100001];
int n,m,i,j,c;
bool v[100001],vv[100001];
void dfs(int k)
{
    int i;
    v[k]=1;
    b.push_back(k);
    for(i=0;i<g[k].size();i++)
        if(!v[g[k][i]])
            dfs(g[k][i]);
}
void dfs2(int k)
{
    int i;
    vv[k]=1;
    comp[c].push_back(k);
    for(i=0;i<gt[k].size();i++)
        if(!vv[gt[k][i]])
            dfs2(gt[k][i]);
}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d %d",&n,&m);
    while(m)
    {
        scanf("%d %d",&i,&j);
        if(i!=j)
        {
            g[i].push_back(j);
            gt[j].push_back(i);
        }
        m--;
    }
    for(i=1;i<=n;i++)
        if(!v[i])
        {
            dfs(i);
            for(j=b.size()-1;j>=0;j--)
                a.push_back(b[j]);
            b.clear();
        }
    for(i=a.size()-1;i>=0;i--)
        if(!vv[a[i]])
        {
            c++;
            dfs2(a[i]);
        }
    printf("%d\n",c);
    for(i=1;i<=c;i++,printf("\n"))
        for(j=0;j<comp[i].size();j++)
            printf("%d ",comp[i][j]);
    return 0;
}