Cod sursa(job #1942324)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 27 martie 2017 22:01:03
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
#include <vector>
#include <stack>
#define nmax 100005
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m,k,t,niv[nmax],low[nmax],in[nmax];
vector <int> v[nmax],r[nmax];
stack <int> s;


void dfs(int x)
{
    int i,y;
    ++k;
    niv[x]=k;
    low[x]=k;
    s.push(x);
    in[x]=1;
    for (i=0;i<v[x].size();i++) {
        y=v[x][i];
        if (niv[y]==0) {
            dfs(y);
            low[x]=min(low[x],low[y]);
        }
        else
            if (in[y])
                low[x]=min(low[x],low[y]);
    }
    if (niv[x]==low[x]) {
        t++;
        do {
            y=s.top();
            s.pop();
            in[y]=0;
            r[t].push_back(y);
        } while (x!=y);
    }
}
int main()
{
    int i,j,l;
    f>>n>>m;
    for (i=1;i<=m;i++) {
        f>>j>>l;
        v[j].push_back(l);
    }
    for (i=1;i<=n;i++)
        if (!niv[i])
            dfs(i);
    g<<t<<'\n';
    for (i=1;i<=t;i++) {
        for (j=0;j<r[i].size();j++)
            g<<r[i][j]<<' ';
        g<<'\n';
    }
    return 0;
}