Cod sursa(job #2174917)

Utilizator tiberiu.bucur17Tiberiu Constantin Emanoil Bucur tiberiu.bucur17 Data 16 martie 2018 14:13:12
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int Maxn=100001;
vector <int>g[Maxn],t[Maxn],comp[Maxn];
int v[Maxn],st[Maxn],vf,co;
bool viz[Maxn];
void dfs(int nod)
{
    viz[nod]=true;
    for(size_t i=0;i<g[nod].size();i++)
        if(!viz[g[nod][i]])
            dfs(g[nod][i]);
    st[++vf]=nod;
}
void dfstrans(int nod)
{
    viz[nod]=true;
    comp[co].push_back(nod);
    for(size_t i=0;i<t[nod].size();i++)
        if(!viz[t[nod][i]])
            dfstrans(t[nod][i]);
}
inline bool cmp(int x,int y)
{
    return comp[v[x]][0]<comp[v[y]][0];
}
int main()
{
    FILE *fin,*fout;
    fin=fopen("ctc.in","r");
    fout=fopen("ctc.out","w");
    int n,m,x,y;
    fscanf(fin,"%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        fscanf(fin,"%d%d",&x,&y);
        g[x].push_back(y);
        t[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
        if(!viz[i])
            dfs(i);
    memset(viz,false,sizeof(viz));
    while(vf)
    {
        x=st[vf--];
        if(!viz[x])
        {
            dfstrans(x);
            sort(comp[co].begin(),comp[co].end());
            v[co]=co;co++;
        }
    }
    sort(v,v+co,cmp);
    fprintf(fout,"%d\n",co);
    for(int i=0;i<co;i++)
    {
        x=v[i];
        for(size_t j=0;j<comp[x].size();j++)
            fprintf(fout,"%d ",comp[x][j]);
        fputc('\n',fout);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}