Cod sursa(job #3258328)

Utilizator ShadowZoidPorojan Victor-Andrei ShadowZoid Data 22 noiembrie 2024 08:19:46
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int n, i, j, k, nr[100005],low[100005],X,g,ctc,s[100005],m,x,y;
vector <int> v[200005],sol[100005];
bool in[100005];
int dfs(int x)
{
    s[++k]=x;
    in[x]=true;
    g++;
    low[x]=g;
    nr[x]=g;
    for(int i=0;i<v[x].size();i++)
        if(nr[v[x][i]]==0)
        {
            dfs(v[x][i]);
            low[x]=min(low[x],low[v[x][i]]);
        }
        else
            if(in[v[x][i]]==1)
        {
            low[x]=min(low[x],low[v[x][i]]);
        }
    if(low[x]==nr[x])
    {
        ctc++;
        do
        {
           X=s[k];
           k--;
           sol[ctc].push_back(X);
           in[X]=0;
        }while(X!=x);
    }
}
int main ()
{
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>x>>y;
        v[x].push_back(y);
    }
    for(i=1;i<=n;i++)
        if(nr[i]==0)
            dfs(i);
    cout<<ctc<<"\n";
    for(i=1;i<=ctc;i++,cout<<"\n")
        for(j=0;j<sol[i].size();j++)
            cout<<sol[i][j]<<" ";
    return 0;
}