Pagini recente » Cod sursa (job #2670279) | Cod sursa (job #1582) | Cod sursa (job #2743671) | Cod sursa (job #825770) | Cod sursa (job #954816)
Cod sursa(job #954816)
#include <fstream>
#include <vector>
using namespace std;
int n, m, nctc=-1;
vector <int> muchii1[100011];
vector <int> muchii2[100011];
vector <int> noduri;
vector <int> ctc[100011];
void citire()
{
ifstream f("ctc.in");
f>>n>>m;
for(int i=0; i<m; i++)
{
int a, b;
f>>a>>b;
muchii1[a].push_back(b);
muchii2[b].push_back(a);
}
f.close ();
}
int viz[100011];
void dfs1 (int nod)
{
viz[nod]=1;
for(int i=0; i<muchii1[nod].size(); i++)
{
if (!viz[muchii1[nod][i]])
dfs1 (muchii1[nod][i]);
}
noduri.push_back(nod);
}
void scriere()
{
ofstream f("ctc.out");
f<<nctc+1<<endl;
for(int i=0; i<=nctc; i++)
{
for(int j=0; j<ctc[i].size(); j++)
f<<ctc[i][j]<< " ";
f<<endl;
}
f.close ();
}
void dfs2 (int nod)
{
viz[nod]=1;
ctc[nctc].push_back(nod);
for(int i=0; i<muchii2[nod].size(); i++)
if(!viz[muchii2[nod][i]])
dfs2(muchii2[nod][i]);
}
int main ()
{
citire ();
for (int i=1; i<=n; i++)
if (!viz[i])
dfs1(i);
memset(viz, 0, sizeof (viz));
for(; !noduri.empty(); noduri.pop_back())
if(!viz[noduri.back()])
{
++nctc;
dfs2(noduri.back());
}
scriere ();
return 0;
}