Pagini recente » Profil popoiu.george | Profil ElizaT | Cod sursa (job #3122892) | Cod sursa (job #160809) | Cod sursa (job #1216652)
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int> A[200001];
vector <int> At[200001];
vector <int> C[200001];
stack <int> S;
int N, M,nrc;
int i, a, b;
int viz[200001];
void df(int v)
{
vector <int>::iterator it;
int w;
viz[v] = 1;
for (it = A[v].begin(); it != A[v].end(); it++)
{
w = *it;
if (!viz[w])
df(w);
}
S.push(v);
}
void ctc(int v)
{
vector<int>::iterator it;
viz[v] = 1;
int w;
C[nrc].push_back(v);
for (it = At[v].begin(); it != At[v].end(); it++)
{
w = *it;
if(!viz[w])
ctc(w);
}
}
int main()
{
f >> N >> M;
for (i = 1; i <= M; i++)
{
f >> a >> b;
A[a].push_back(b);
At[b].push_back(a);
}
for (i = 1; i <= N; i++)
if (!viz[i])
df(i);
for (i = 1; i <= N; i++)
viz[i] = 0;
while (!S.empty())
{
int v;
v = S.top();
S.pop();
if (!viz[v])
{
nrc++;
ctc(v);
}
}
g << nrc << '\n';
for (i = 1; i <= nrc; i++)
{
vector<int>::iterator it;
for (it = C[i].begin(); it != C[i].end(); it++)
g << *it << ' ';
g << '\n';
}
f.close();
g.close();
return 0;
}