Cod sursa(job #2522516)

Utilizator BogdanGhGhinea Bogdan BogdanGh Data 12 ianuarie 2020 17:12:42
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <bits/stdc++.h>
using namespace std;
int nr,pos,buff_size=1<<16;
char buff[1<<17];
inline void read(int &nr)
{
    while(buff[pos] < '0' || buff[pos] > '9')
        if(++pos == buff_size)
            fread(buff,  1,buff_size, stdin), pos = 0;
    nr = 0;
    while('0' <= buff[pos] && buff[pos] <= '9')
    {
        nr = nr * 10 + buff[pos] - '0';
        if(++pos == buff_size)
            fread(buff, 1, buff_size, stdin), pos = 0;
    }
}
ofstream g("ctc.out");
const int nmax=100005;
int n,x,y,i,j,m,id[nmax],low[nmax],k,sol,ok;
bool viz[nmax],onstack[nmax];
stack <int>st;
vector <int>v[300];
void dfs(int nod)
{
    viz[nod]=1;
    id[nod]=low[nod]=++k;
    onstack[nod]=1;
    st.push(nod);
    for(auto i:v[nod])
    {
        if(!viz[i])
            dfs(i);
        if(onstack[i])
            low[nod]=min(low[nod],low[i]);
    }
    if(id[nod]==low[nod])
    {
        for(x=st.top();; x=st.top())
        {
            if(ok)
                g<<x<<' ';
            st.pop();
            onstack[x]=0;
            low[x]=id[nod];
            if(x==nod)break;
        }
        sol++;
        if(ok)g<<'\n';
    }
}
int main()
{
    freopen("ctc.in","r",stdin);
    read(n);
    read(m);
    for(i=1; i<=m; i++)
    {
        read(x);
        read(y);
        v[x].push_back(y);
    }
    for(i=1; i<=n; i++)
        if(!viz[i])
            dfs(i);
    g<<sol<<'\n';
    ok=1;
    for(i=1;i<=n;i++)
        viz[i]=0;
    for(i=1; i<=n; i++)
        if(!viz[i])
            dfs(i);
    return 0;
}