Cod sursa(job #2278761)

Utilizator driver71528@gmail.comTerec Andrei-Sorin [email protected] Data 8 noiembrie 2018 15:31:05
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>
#include <iterator>
#define MAXn 100000
#define UNVISITED -1
using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

vector<int> v[MAXn+1];
stack<int> s;
bool onstack[MAXn+1];
int id[MAXn+1],low[MAXn+1];
int ID,n,m,nr;

vector< vector<int> >rez;
vector <int> c;

void tarjan(int i)
{
    id[i]=low[i]=ID++;
    s.push(i);
    onstack[i]=true;
    for(vector<int>::iterator it=v[i].begin();it!=v[i].end();it++)
    {
        if(id[*it]==UNVISITED)
            tarjan(*it);
        if(onstack[*it])
            low[i]=min(low[i],low[*it]);
    }
    if(id[i]==low[i])
    {
        c.clear();
        int node;
        do
        {
            c.push_back(s.top());
            node=s.top();
            onstack[node]=false;
            s.pop();
        }while(node!=i);
        rez.push_back(c);
        nr++;
    }
}

int main()
{
    f>>n>>m;
    int a,b;
    for(int i=1;i<=m;i++)
    {
        f>>a>>b;
        v[a].push_back(b);
    }
    for(int i=1;i<=n;i++)
        id[i]=UNVISITED;
    for(int i=1;i<=n;i++)
        if(id[i]==UNVISITED)
        {
            tarjan(i);
        }
    g<<nr;
    for(size_t i=0;i<rez.size();i++)
    {
        g<<'\n';
        for(size_t j=0;j<rez[i].size();j++)
            g<<rez[i][j]<<' ';
    }
    f.close();
    g.close();
    return 0;
}