Pagini recente » Cod sursa (job #886892) | Cod sursa (job #1377435) | Cod sursa (job #1680486) | Cod sursa (job #2087952) | Cod sursa (job #3226906)
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector<int> G[100001],GT[100001],ctc[100001];
vector<int> S;
bool viz[100001];
int n,m,nrc;
void dfs(int nod)
{
int i;
viz[nod] = true;
for(i = 0; i < G[nod].size(); i++)
{
int nod_next = G[nod][i];
if(viz[nod_next] == false)
dfs(nod_next);
}
S.push_back(nod);
}
void tdfs(int nod)
{
int i;
viz[nod] = true;
ctc[nrc].push_back(nod);
for(i = 0; i < GT[nod].size(); i++)
{
int nod_next = GT[nod][i];
if(viz[nod_next] == false)
tdfs(nod_next);
}
}
int main()
{
int i,a,b;
f>>n>>m;
nrc = 0;
for(i = 1; i <= m; i++)
{
f>>a>>b;
G[a].push_back(b);
GT[b].push_back(a);
}
for(i = 1; i <= n; i++)
{
if(viz[i] == false)
dfs(i);
}
for(i = 1; i <= n; i++)
{
viz[i] = false;
}
for(i = S.size()-1; i >= 0; i--)
{
int nod = S[i];
if(viz[nod] == false)
{
nrc++;
tdfs(nod);
}
}
g<<nrc<<'\n';
for(i = 1; i <= nrc; i++)
{
for(int j = 0; j < ctc[i].size(); j++)
{
g<<ctc[i][j]<<" ";
}
g<<'\n';
}
return 0;
}