Pagini recente » Cod sursa (job #339057) | Istoria paginii runda/343242354534 | Cod sursa (job #478456) | Cod sursa (job #2767842) | Cod sursa (job #1252815)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
vector <int>L[100003];
vector <int>p[100003];
vector <int>tr[100003];
int n, m,k;
int V[100003], V2[100003];
int tf[100003], ctc[1000003];
ifstream fin("ctc.in");
void Citire()
{
fin >> n >> m; //m-numarul de muchii; n-nr de noduri
int i, x, y;
for (i = 1; i <= m; i++)
{
fin >> x >> y;
L[x].push_back(y);
}
}
void DFS_timp_final(int x)
{
V2[x] = 1;
for (unsigned int i = 0; i < L[x].size(); i++)
if (V2[L[x][i]] == 0)
DFS_timp_final(L[x][i]);
tf[++k]=x;
}
void Graf_Transpus()
{
int len, i, j, k;
for(i = 1; i <= n; i++)
{
len = L[i].size();
for(j = 0; j < len; j++)
{
k = L[i][j];
tr[k].push_back(i);
}
}
}
void DFS_tr(int x)
{
V[x] = 1;
ctc[x]=k;
for (unsigned int i = 0; i < tr[x].size(); i++)
if (V[tr[x][i]] == 0)
DFS_tr(tr[x][i]);
}
void Afisare()
{
ofstream fout("ctc.out");
int i,j;
fout<<k<<"\n";
for (i = 1; i <= k; i++)
{
for(j=1;j<=n;j++)
if(ctc[j]==i)
fout <<j <<" ";
fout<<" ";
}
fout<<"\n";
}
int main()
{
int i,x;
Citire();
Graf_Transpus();
k=0;
for(i=1;i<=n;i++)
if(!V2[i])
DFS_timp_final(i);
k=0;
for(i=n;i>=1;i--)
{
if(V[tf[i]]==0)
{
k++;
DFS_tr(tf[i]);
}
}
Afisare();
return 0;
}