Cod sursa(job #2302179)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 13 decembrie 2018 21:47:26
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include<fstream>
#include<stack>
#include<vector>
#include<algorithm>
#include<iterator>
using namespace std;
#define N 100001
vector<int> a[N],con,idx,lowlink,in_stack;
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)
{
    idx[n]=lowlink[n]=l;
    l++,s.push(n),in_stack[n]=1;
    vector<int>::const_iterator j;
    for(j=a[n].begin();j!=a[n].end();j++)
        if(idx[*j]==-1)
            T(*j,adj),lowlink[n]=min(lowlink[n],lowlink[*j]);
        else if(in_stack[*j])
            lowlink[n]=min(lowlink[n],lowlink[*j]);
    if(idx[n]==lowlink[n])
    {
        con.clear();
        int o;
        do
            con.push_back(o=s.top()),s.pop(),in_stack[o]=0;
        while(o!=n);
        c.push_back(con);
    }
}
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);
    idx.resize(n),lowlink.resize(n),in_stack.resize(n),idx.assign(n,-1),in_stack.assign(n,0);
    for(i=0;i<n;i++)
        if(idx[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";
    }
}