Cod sursa(job #2302183)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 13 decembrie 2018 21:52:52
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include<fstream>
#include<stack>
#include<vector>
#include<algorithm>
#include<iterator>
using namespace std;
#define N 100001
vector<int> a[N],o,z,w,t;
vector<vector<int>> c;
stack<int> s;
int l,n,i,j,x,y,e,k;
void T(const int n,const vector<int> *a)
{
    z[n]=w[n]=l;
    l++,s.push(n),t[n]=1;
    vector<int>::const_iterator j;
    for(j=a[n].begin();j!=a[n].end();j++)
        if(z[*j]==-1)
            T(*j,a),w[n]=min(w[n],w[*j]);
        else if(t[*j])
            w[n]=min(w[n],w[*j]);
    if(z[n]==w[n])
    {
        o.clear();
        int r;
        do
            o.push_back(r=s.top()),s.pop(),t[r]=0;
        while(r!=n);
        c.push_back(o);
    }
}
int main(void)
{
    ifstream f("ctc.in");
    ofstream g("ctc.out");
    f>>n;
    for(f>>e;e>0;e--)
        f>>x>>y,a[x-1].push_back(y-1);
    z.resize(n),w.resize(n),t.resize(n),z.assign(n,-1),t.assign(n,0);
    for(i=0;i<n;i++)
        if(z[i]==-1)
            T(i,a);
    k=c.size();
    g<<k<<"\n";
    for(i=0;i<k;i++)
    {
        for(j=0;j<c[i].size();j++)
            g<<c[i][j]+1<<" ";
        g<<"\n";
    }
}