Pagini recente » Cod sursa (job #3217052) | Cod sursa (job #949703) | Cod sursa (job #2439100) | Cod sursa (job #1638103) | Cod sursa (job #1250472)
#include <fstream>
#include <vector>
#define NMAX 100001
using namespace std;
ofstream fout ("ctc.out");
int n, m, nr;
vector <int> A[NMAX], AT[NMAX], sol[NMAX], postordine;
bool uz[NMAX], uztr[NMAX];
void citire();
void dfs(int poz);
void dfstr(int poz);
void afisare();
int main()
{
int i;
citire();
for(i=1; i<=n; i++)
if(!uz[i])
dfs(i);
afisare();
return 0;
}
void citire()
{
ifstream fin ("ctc.in");
fin>>n>>m;
int x, y, i;
for(i=1; i<=m; ++i)
{
fin>>x>>y;
A[x].push_back(y);
AT[y].push_back(x);
}
fin.close();
}
void dfs(int poz)
{
uz[poz]=true;
int i;
for(i=0; i<A[poz].size(); ++i)
{
if(!uz[A[poz][i]])
{
dfs(A[poz][i]);
}
}
postordine.push_back(poz);
}
void dfstr(int poz)
{
uztr[poz]=true;
sol[nr].push_back(poz);
int i;
for(i=0; i<AT[poz].size(); ++i)
{
if(!uztr[AT[poz][i]])
{
dfstr(AT[poz][i]);
}
}
}
void afisare()
{
int i, j;
for(i=n-1; i>=0; --i)
{
if(!uztr[postordine[i]])
{
++nr;
dfstr(postordine[i]);
}
}
fout<<nr<<'\n';
for(i=1; i<=nr; ++i)
{
for(j=0; j<sol[i].size(); ++j)
fout<<sol[i][j]<<' ';
fout<<'\n';
}
fout.close();
}