Cod sursa(job #2468032)

Utilizator iulianarsenoiuArsenoiu Iulian iulianarsenoiu Data 5 octombrie 2019 11:54:00
Problema Componente tare conexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int> g1[100005],g2[100005],v[100005];
stack <int> st;
vector <int> :: iterator it;
bool sel[100005];
int n,m,i,nr,x,y;
void dfs(int x)
{
    sel[x]=true;
    for(auto it : g1[x])
        if(!sel[it])
        dfs(it);
    st.push(x);
}
void dfs2(int x)
{
    sel[x]=true;
    v[nr].push_back(x);
    for(auto it : g2[x])
        if(!sel[it])
        dfs2(it);
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        g1[x].push_back(y);
        g2[y].push_back(x);
    }
    for(i=1;i<=n;i++)
    {
        if(!sel[i])
            dfs(i);
    }
    for(i=1;i<=n;i++)
        sel[i]=false;
    while(!st.empty())
    {
        x=st.top();
        if(!sel[x]){
            nr++;
            dfs2(x);
        }
        st.pop();
    }
    g<<nr<<'\n';
    for(i=1;i<=nr;i++)
    {
        if(v[i].size()>1)
        for(auto it : v[i])
            g<<it<<' ';
        g<<'\n';
    }
    return 0;
}