Pagini recente » Cod sursa (job #1621923) | Cod sursa (job #1102710) | Cod sursa (job #1077544) | Cod sursa (job #1571059) | Cod sursa (job #3347968)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
const int mxN = 1e5 + 1;
vector<int> G[mxN], Gt[mxN];
stack<int> ordine;
int n, m, componenta[mxN];
bool parcurs[mxN];
void DFS(int nod){
parcurs[nod] = true;
for(auto x : G[nod]){
if(!parcurs[x])
DFS(x);
}
ordine.push(nod);
}
void conex(int nod, int culoare){
componenta[nod] = culoare;
for(auto x : Gt[nod]){
if(!componenta[x])
conex(x, culoare);
}
}
int main(){
int cul = 0;
fin >> n >> m;
for(int i = 1; i <= m; i++){
int a, b;
fin >> a >> b;
G[a].push_back(b);
Gt[b].push_back(a);
}
for(int i = 1; i <= n; i++){
if(!parcurs[i])
DFS(i);
}
while(!ordine.empty()){
if(!componenta[ordine.top()])
conex(ordine.top(), ++cul);
ordine.pop();
}
fout << cul << "\n";
vector<vector<int>> comp(cul + 1);
for(int i = 1; i <= n; i++)
comp[componenta[i]].push_back(i);
for(int c = 1; c <= cul; c++){
for(auto x : comp[c])
fout << x << " ";
fout << "\n";
}
}