Pagini recente » Cod sursa (job #2576200) | Cod sursa (job #1358726) | Cod sursa (job #3304529) | Cod sursa (job #2559954) | Cod sursa (job #3337759)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, a, b, vis[100001], ct;
vector<int> AD[100001], ADT[100001], comp[50001];
stack<int> s;
void DFS(int nod)
{
vis[nod] = 1;
for (int i = 0; i < AD[nod].size(); i++)
{
int w = AD[nod][i];
if (vis[w] == 0)
DFS(w);
}
s.push(nod);
}
void DFST(int nod)
{
vis[nod] = 2;
for (int i = 0; i < ADT[nod].size(); i++)
{
int w = ADT[nod][i];
if (vis[w] == 1)
{
DFST(w);
}
}
comp[ct].push_back(nod);
}
int main()
{
fin >> n >> m;
for (int i = 1; i <= m; i++)
{
fin >> a >> b;
AD[a].push_back(b);
ADT[b].push_back(a);
}
for (int i = 1; i <= n; i++)
if (vis[i] == 0)
DFS(i);
while (s.size() != 0)
{
int i = s.top();
s.pop();
if (vis[i] == 1)
{
ct++;
DFST(i);
}
}
fout << ct;
for (int i = 1; i <= ct; i++)
{
fout << "\n";
for (int j = 0; j < comp[i].size(); j++)
fout << comp[i][j] << " ";
}
return 0;
}