Cod sursa(job #1456641)

Utilizator cojocarugabiReality cojocarugabi Data 1 iulie 2015 14:36:31
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
# include <bits/stdc++.h>
using namespace std;
ifstream fi("ctc.in");
ofstream fo("ctc.out");
vector < int > s[100005];
vector < int > v[100005];
bitset < 100005 > b;
vector < int > order;
vector < int > c;
vector < vector < int > > ans;
void dfs1(int nod)
{
    b[nod] = 1;
    for (vector < int > :: iterator it = s[nod].begin();it != s[nod].end();++it)
        if (!b[*it]) dfs1(*it);
    order.push_back(nod);
}
void dfs2(int nod)
{
    b[nod] = 0;
    c.push_back(nod);
    for (vector < int > :: iterator it = v[nod].begin();it != v[nod].end();++it)
        if (b[*it]) dfs2(*it);
}
int main(void)
{
    int n,m;
    fi>>n>>m;
    int x,y;
    while (m --)
    {
        fi>>x>>y;
        s[x].push_back(y);
        v[y].push_back(x);
    }
    for (int i = 1;i <= n;++i) if (!b[i]) dfs1(i);
    for (int i = n-1;i+1;--i) if (b[order[i]])
    {
        dfs2(order[i]);
        ans.push_back(c);
        c.clear();
    }
    fo << ans.size() << '\n';
    for (vector < vector < int > > :: iterator it = ans.begin();it != ans.end();++it)
    {
        for (vector < int > :: iterator i = (*it).begin();i != (*it).end();++i) fo << *i << ' ';
        fo << '\n';
    }
    return 0;
}