Pagini recente » Cod sursa (job #946203) | Cod sursa (job #1958537) | Cod sursa (job #1828875) | Cod sursa (job #900241) | Cod sursa (job #2375573)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
int n, m, x, y, cnx;
vector <int> G[100005], GT[100005], v, N[100005];
bitset <100005> viz1, viz;
void DFS (int nod)
{
int curent;
viz[nod] = 1;
for (int i=0; i<G[nod].size(); i++)
{
curent = G[nod][i];
if (!viz[curent]) DFS(curent);
}
v.push_back(nod);
}
void DFS1 (int nod)
{
int curent;
viz1[nod] = 1;
N[cnx].push_back(nod);
for (int i=0; i<GT[nod].size(); i++)
{
curent = GT[nod][i];
if (!viz1[curent]) DFS1(curent);
}
}
int main()
{
fin >> n >> m;
while(m--)
{
fin >> x >> y;
G[x].push_back(y);
GT[y].push_back(x);
}
for (int i=1; i<=n; i++)
if (viz[i] == 0) DFS(i);
for (int i=v.size()-1; i>=0; i--)
if (!viz1[v[i]])
{
cnx++;
DFS1(v[i]);
sort(N[cnx].begin(), N[cnx].end());
}
fout << cnx << "\n";
int curent;
for (int i=1; i<=cnx; i++)
{
for (int j=0; j<N[i].size(); j++)
fout << N[i][j] << " ";
fout << "\n";
}
return 0;
}