Pagini recente » Cod sursa (job #384726) | Cod sursa (job #2734849) | Cod sursa (job #1708730) | Cod sursa (job #1245941) | Cod sursa (job #2871008)
#include <bits/stdc++.h>
#define Dmax 100005
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m,nrCTC;
stack<int>S;
vector<int>G[Dmax],GT[Dmax],CTC[Dmax];
bool viz1[Dmax],viz2[Dmax];
void DFS1(int nod)
{
viz1[nod] = true;
for(vector<int>::iterator it = G[nod].begin(); it < G[nod].end(); it++)
{
int Vecin = *it;
if(!viz1[Vecin])
DFS1(Vecin);
}
S.push(nod);
}
void DFS2(int nod)
{
viz2[nod] = true;
for(vector<int>::iterator it = GT[nod].begin(); it < GT[nod].end(); it++)
{
int Vecin = *it;
if(!viz2[Vecin])
DFS2(Vecin);
}
CTC[nrCTC].push_back(nod);
}
int main()
{
f>>n>>m;
for(int i = 1; i <= m; i++)
{
int x,y;
f>>x>>y;
G[x].push_back(y);
GT[y].push_back(x);
}
for(int i = 1; i <= n; i++)
if(!viz1[i])
DFS1(i);
while(!S.empty())
{
if(!viz2[S.top()])
{
nrCTC++;
DFS2(S.top());
}
S.pop();
}
sort(CTC+1,CTC+1+nrCTC);
for(int i = 1; i <= nrCTC; i++)
sort(CTC[i].begin(),CTC[i].end());
g<<nrCTC<<"\n";
for(int i = 1; i <= nrCTC; i++,g<<"\n")
for(vector<int>::iterator it = CTC[i].begin(); it < CTC[i].end(); it++)
g<<*it<<" ";
return 0;
}