Pagini recente » Monitorul de evaluare | Rating Tatar Lavinia (alllaballla) | Cod sursa (job #403009) | Cod sursa (job #1048840) | Cod sursa (job #384779)
Cod sursa(job #384779)
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
#define MAX_N 100005
#define foreach(V) for(typeof (V).begin() it = (V).begin(); it != (V).end(); ++it)
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
int N, M, Nrc, S[MAX_N];
vector <int> Gin[MAX_N], Gout[MAX_N], C[MAX_N];
bitset <MAX_N> viz;
void citire()
{
fin >> N >> M;
for(int i = 1; i <= M; ++i)
{
int x, y;
fin >> x >> y;
Gout[x].push_back(y);
Gin[y].push_back(x);
}
}
void DFP(int nod)
{
viz[nod] = 1;
foreach(Gout[nod])
if(viz[*it] == 0)
DFP(*it);
S[++S[0]] = nod;
}
void DFM(int nod)
{
viz[nod] = 1;
C[Nrc].push_back(nod);
foreach(Gin[nod])
if(viz[*it] == 0)
DFM(*it);
}
void solve()
{
for(int i = 1; i <= N; ++i)
if(viz[i] == 0)
DFP(i);
viz.reset();
for(int i = S[0]; i; --i)
if(viz[S[i]] == 0)
{
++Nrc;
DFM(S[i]);
}
fout << Nrc << "\n";
for(int i = 1; i <= Nrc; ++i)
{
foreach(C[i])
fout << *it << " ";
fout << "\n";
}
}
int main()
{
citire();
solve();
}