Pagini recente » Cod sursa (job #2475712) | Cod sursa (job #321453) | Cod sursa (job #3196070) | Cod sursa (job #561616) | Cod sursa (job #2293714)
#include <iostream>
#include <fstream>
#include <vector>
#define maxN 100001
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
void citire(int &n, int &m, vector<int> v[]) {
int x,y;
fin>>n>>m;
for (int i=1; i<=m; ++i) {
fin>>x>>y;
v[x].push_back(y);
}
}
void Tarjan(int x, vector<int> v[], int idx[], int lowlink[], int st[], bool inQ[], vector<vector<int>>& ctc) {
st[++st[0]]=x;
inQ[x]=true;
idx[x]=++idx[0];
lowlink[x]=idx[0];
for (int i=0; i<v[x].size(); ++i) {
if (!idx[v[x][i]]) Tarjan(v[x][i], v, idx, lowlink, st, inQ, ctc);
if (inQ[v[x][i]])
lowlink[x] = min(lowlink[x], lowlink[v[x][i]]);
}
if (idx[x]==lowlink[x]) {
ctc.push_back(vector <int>());
while (st[st[0]]!=x) {
ctc.back().push_back(st[st[0]]);
inQ[st[st[0]]]=false;
--st[0];
}
ctc.back().push_back(x);
inQ[x]=false;
--st[0];
}
}
int main() {
int n, m;
vector <int> v[maxN];
vector < vector <int> > ctc;
bool inQ[maxN]={0};
int idx[maxN]={0}, lowlink[maxN]={0}, st[maxN]={0};
citire(n,m,v);
for (int i=1; i<=n; ++i)
if (!idx[i]) Tarjan(i, v, idx, lowlink, st, inQ, ctc);
fout<<ctc.size()<<'\n';
for (int i=0; i<ctc.size(); ++i) {
for (vector <int>::iterator it=ctc[i].begin(); it!=ctc[i].end(); ++it)
fout<<*it<<' ';
fout<<'\n';
}
return 0;
}