Pagini recente » Cod sursa (job #963505) | Cod sursa (job #2827166) | Cod sursa (job #1653385) | Cod sursa (job #3250998) | Cod sursa (job #2957058)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
struct compcon {
vector<int> noduri;
} c[100005];
struct nod {
int index, low, viz;
} N[100005];
stack<int> S;
vector<int> G[100005];
int n, m, nrc, timp;
void citire() {
fin>>n>>m;
int x, y;
for (int i=0; i<m; i++) {
fin>>x>>y;
G[x].push_back(y);
}
}
void dfs(int k) {
N[k].index=timp;
N[k].low=timp;
timp++;
S.push(k);
N[k].viz=1;
for (auto i: G[k])
if (!N[i].index) {
dfs(i);
N[k].low=min(N[k].low, N[i].low);
} else if (N[i].viz) {
N[k].low=min(N[k].low, N[i].index);
}
if (N[k].low==N[k].index) {
int w;
do {
w=S.top();
c[nrc].noduri.push_back(w);
N[k].viz=0;
S.pop();
} while (w!=k && !S.empty());
nrc++;
}
}
void parcurgere() {
for (int i=1; i<=n; i++)
if (!N[i].index)
dfs(i);
}
void afisare() {
fout<<nrc<<"\n";
for (int i=0; i<nrc; i++) {
for (auto j: c[i].noduri)
fout<<j<<" ";
fout<<"\n";
}
}
int main() {
citire();
parcurgere();
afisare();
return 0;
}